The Research On Some Problems Related To Hamiltonicity Of Graphs

The hamiltonian problem is a classical topic in structural graph theory,which is closely related to Four Color Problem.Hamilton problem has been widely used in operational research,communication networks,social networks,computer science,coding theory and complexity theory.Hence lots of graph scholars are dedicated to this topic.In this thesis,we study some problems related to hamiltonian properties of graphs,including connected even factors,hamiltonian cycle,the longest cycle problem,Hamilton-connected problems.The full paper contains seven chapters.In the following,let me explain explicitly what I have done.In Chapter 1,we list some symbols and terminologies,which will be used throughout this thesis.Then,a general survey of this thesis as well as preliminaries on hamiltonian properties,and the development of hamiltonian problems at home and abroad are given.We also introduce the structure of this thesis,including the research content and main results.In Chapter 2,we introduce the concept of H-free graphs,and study the existence con-ditions of connected even factors.It is proved that if G is a connected,locally connected K1,s+2-free graph of order p>3,then G has a connected even[2,2s]-factor.In Chapter 3,we give sufficient conditions to judge the hamiltonian property by using induced cycle.It is proved that every 3-connected line graph such that every induced cycle is of length at most 8 is hamiltonian,and this result can be extended into o-heavy graph.It is shown that every 3-connected claw-free graph such that every induced cycle of length at least 4 has at most 8 edges contained in a triangle is hamiltonian.We also show that every 3-connected claw-free graph whose every induced cycle of length at least 4 has at most 11 edges contained in a triangle is hamiltonian or its closure is line graph of the graph contractible to the Petersen graph.Every 2-connected claw-free graph of longest induced cycle with length at least n-2 is hamiltonian.These results are all best possible.In Chapter 4,we obtain the following:let G be a claw-free graph with n vertices and minimum degree ?(G)?3.If G has an induced cycle of length more than 4n-2?(G)-4/?(G)-2,then G is hamiltonian.The result is best possible for ?(G)? {3,4}.Although we do not know whether it is also best possible for ? ? 5,some example shows the best possible bound may not less than 4n-2?-4/?+2.In Chapter 5,we prove that:let G be a graph of connectivity ?(G)? k ? 2 and of order n ? 2k + 1,then every longest cycle of G contains all vertices of degree at least d = max {[n/2],n-3k + 2}.Using an additional condition of independent number,we have that:let G be a k-connected graph of order n and of independent number ?,then every longest cycle of G contains all vertices of degree more than d0=(?-k)n-k?+k2+?2-2?/?.In Chapter 6,we introduce the concept and property of SM-closure of G.In what additional conditions may guarantee that "G is Hamilton-connected if and only if the closure cl(G)of G is Hamilton-connected"?The result is that if G is a 2-connected claw-free graph with minimum degree at least 3 such that its SM-closure GM is hourglass-free,then G is hamilton-connected if and only if the closure cl(G)of G is hamilton-connected.In Chapter 7,we give a conclusion.In this chapter,the main contribution of this thesis is summarized and the expectation is made.