Heavy Subgraph Conditions For Hamiltonicity Of Graphs And Related Topics

A graph is said to be hamiltonian,if it contains a Hamilton cycle,i.e.,a cycle passing through all vertices of the graph.In the thesis we study a kind of sufficient conditions for hamiltonicity of graphs,namely heavy subgraph condi-tions.The research addresses the following questions:We already knew a graph is hamiltonian if we forbidden some subgraph construction.Now if such a con-struction exists,how we can restrict to this construction and still guarantee that the given graph has a Hamilton cycle?For a given graph H,a graph G is said to be H-free,if G does not contain induced copies of H.In 1991,Bedrossian characterized in his Ph.D thesis all pairs of connected graphs {R,S} such that every 2-connected R-free S-free graph is hamiltonian.Let P be some property of subgraphs of a graph G.For a given graph H,if every induced subgraph G' of G isomorphic to H satisfies P,then we say that G satisfies P(H).Clearly if G is H-free,then G satisfies P(H).The main problem addressed in the thesis is:For which graph R and which property P,a graph satisfying P(R)implies that it is hamiltonian.We named such a sufficient condit,ion heavy subgraph condition.So a heavy subgraph condition has two elements:the subgraph R and the restrictive condition P on the subgraph.In this thesis,we study a class of heavy subgraph conditions.For every considered condition,we completely characterize the subgraphs that can ensure a 2-connected graph to be hamiltonian.Besides,we also discuss in the thesis some properties related to hamiltonicity,including the property that every longest cycle passes through all large degree vertices,and the existence of 2-factors.In the first chapter we introduce the basic definitions and background of the topics,and we list our main results of the thesis.In each of' the second to the sixth chapters,we propose a kind of restrictive condition.We study the hamiltonicity of graphs in these conditions.A graph G is said to be H-o-heavy if every induced subgraph of G isomorphic to H contains two nonadjacent vertices with degree sum at least n in G(n is the order of G).In order to research the hamiltonicity of claw-free graphs and claw-o-heavy graphs,Ryjacek and Cada introduced the closure theory of claw-free graphs and claw-o-heavy graphs,respectively.In the second chapt,er we briefly introduce the closure theory,which is one of our main tools.In 2002,Ryjacek described the structure of the closure of claw-free graphs.Motivated by Ryjack's description,we describe the structure of the closure of claw-o-heavy graphs.In the third chapter we consider the degree conditions of the end-vertices of subgraphs.For a given graph H,we say a graph G satisfies?(H,k)if every end-vertex of induced subgraph of G isomorphic to H has degree at least(n-k)/3.In 1993,Broersma proposed a conjecture that every 2-connected claw-free graph satisfying?(N,-2)is hamiltonian.In the third chapter we characterize all the connected graphs R such that every 2-connected claw-free graph satisfying?(R,3)is hamiltonian.Our result give a partly answer to Broersma's conjecture.In the fourth chapter we consider the c-heavy subgraph conditions of the hamiltonicity of claw-o-heavy graphs.For a given graph H,the graph G is said to be H-c-heavy,if for every induced subgraph G? of G isomorphic to H and every maximal clique C of G? every nont,rivial component of G?-C has a vertex with degree at least n/2 in G.We completely characterize all the connected graphs R such that every 2-connected claw-o-heavy R-c-heavy graph is hamiltonian.In the fifth chapter we consider the p-heavy subgraph conditions of the hamiltonicity of claw-o-heavy graphs.For a given connected graph H,the graph G is said to be H-p-heavy,if every induced subgraph of G isomorphic to H has either only one center and with degree n/2 or has two centers with degree sum at least n in G.We characterize all the graphs R such that every 2-connected claw-o-heavy R-p-heavy graph is hamiltonian.A graph G is said to be 1-tough if for every vertex cut S of G,the component number of G-S is at most |S|.Clearly every hamiltonian graph is 1-tough.In the sixth chapter we consider the forbidden subgraph conditions for hamiltonicity of 1-tough graphs.We almost establish all the subgraphs R such that every 1-tough R-free graph of order at least 3 is hamiltonian.In the seventh and eighth chapters,we discuss the forbidden subgraph condi-tions and heavy subgraph conditions for properties that related to hamiltonicity of graphs.In the seventh chapter we study the property that every longest cycle con-tans all the vertices with large degree in graphs.For a given number ?<1,we consider that for which graph R,a 2-connected graph G being R-free implies that every longest cycle contains all vertices of G with degree at least on+O(1).We characterize all connected graphs satisfying such a property.The 2-regular spanning subgraph of a graph is called a 2-factor.In 2008,Faudree et al.characterized all pairs of connected graphs {R,S} such that every 2-connected R-free S-free graph has a 2-factor.In the eighth chapter we discuss the o-heavy subgraph conditions for the existence of 2-factors in graphs.We characterize all pairs of connected graphs {R,S} such that every 2-connected R-o-heavy S-o-heavy graph has a 2-factor.In the last chapter we briefly summarize our work in the thesis and propose some questions that can be further considered.