| In graph theory,paths and cycles of graphs are two basic structures, and tools that is used to analyze and describe graphs.In real life, many practical problems can be attributed to the problem of paths and cycles. So, this problem has been the im-portant hot-spot problem in graph theory. The famous Hamilton problem belongs to the problem of paths and cycles of graphs in essence, it and four-color problem……are three famous difficult problems in graph theory. What is more,many scholars at home and abroad made a lot of research work on this issue. The re-search results and progress in this area can be found in literature. After the development for dozens of years, the contents about the properties of path and cycle become more and more rich and specific. The properties of path include Hamil-ton path (traceability),homogeneous-traceability, longest path, Hamilton-connected,pan-connectivity, path extendsibility and so on; the properties of cycle include Hamilton cycle, Dominating-cycle,longest cycle,(vertex-)pancyclicity, cycle extend-sibility vertex-disjoint cycle,cycle-covered and so on.However, we can not deny that it is difficult to study Hamilton problem in those graphs without any restriction. So we turn to explore the special graphs,such as the graphs not containing some forbidden subgraphs.The condition of degree, neighborhood sum and neighborhood unions becomes an important way to study the problems. In this respect, a lot of outstand achievements have been made. The papers which about the properties of line graph appeared in [27]-[28], and they were written by Seineke in1970s. Then the claw-free graphs that include line graph was concerned. The researh of claw-free graph was very actived in late70s and early80s. Some famous results about claw-free graphs can be seen in. In addition, the definition of claw-free graph has been extended to several larger graph families in different views, such as quasi-claw-free graphs,almost claw-free graphs,etc.In this paper, we mainly discuss the relations between the degree condition(the sum degree of any non-adjacent subgraph) and properties of graphs’ paths and cycles(including Hamilton connected, traceable, Hamilton cycle et).And it gives some sufficient conditions about the properties of paths and cycles in claw-free graphs and quasi-claw-free graphs.In the first chapter, we give a brief introduction about the basic concepts, terminologies and symbols which will be used in this paper. In the meantime, we also give some related research backgrounds and some known results.In the second chapter, we mainly study the properties of paths and cycles with different conditions of degree in claw-free graphs and quasi-claw-free graphs give the following results:Theorem2.1.7Let G be a2-connected claw-free graph of order n, H1, H2, any two non-adjacent subgraphs,are isomorphic to P3and K1respectively, if d(H1)+d(H2)≥n,then G contains Hamilton cycle.Corollary2.1.8Let G be a2-connected claw-free graph of order n,H1,H2, any two non-adjacent subgraphs,are isomorphic to K3and K1respectively, if d(H1)+d(H2)≥n,then G contains Hamilton cycle.Theorem2.2.1Let G be a2-connected quasi-claw-free graph of order n, H1, H2, any two non-adjacent subgraphs,are isomorphic to K2and K2respectively, if d(H1)+d(H2)> n,then G contains Hamilton cycle. Corollary2.2.3Let G be a2-connected quasi-claw-free graph of order n, H1, H2, any two non-adjacent subgraphs,are isomorphic to K2, if d(H1)+d(H2)≥n,then G contains Hamilton cycle.Theorem2.3.2Let G be a3-connected claw-free graph of order n, H1and H2, any two non-adjacent subgraphs, are isomorphic to K3and K2respectively, if d(H1)+d(H2)≥n-3, then G contains Hamilton cycle.Corollary2.3.3Let G be a3-connected claw-free graph of order n,H1and H2, any two non-adjacent subgraphs,are isomorphic to P3and K2respectively, if d(H1)+d(H2)≥n-3, then G contains Hamilton cycle.Corollary2.3.4Let G be a3-connected claw-free graph of order n,H1and H2, any two non-adjacent subgraphs, are isomorphic to K3and K2respectively,if d(H1)+d(H2)≥n-3, then G contains Hamilton cycle.Corollary2.3.5Let G be a3-connected claw-free graph of order n,H1and H2, any two non-adjacent subgraphs, are isomorphic to K3and K2respectively, if d(H1)+d(H2)≥n-3, then G contains Hamilton cycle.Corollary2.3.6Let G be a3-connected claw-free graph of order n, H1and H2, any two non-adjacent subgraphs, are isomorphic to P3and K2respectively, if d(H1)+d(H2)≥n-3, then G contains Hamilton cycle.In the third chapter, we mainly study the properties of Hamilton-connected with different conditions of degree in claw-free graphs and give the following results:Theorem3.1.1Let G be a2-connected graph of order n.δ(G)≥3, H1and H2, any two non-adjacent subgraphs, are isomorphic to K2, if d(H1)+d(H2)≥n-1, then for any two vertex u, v,{u, u}isn’t a cut set, then exit a Hamilton path between u and v.Corollary3.1.2Let G be a3-connected graph of order n. H1and H2,any two non-adjacent subgraphs,are isomorphic to K2, if d(H1)+d(H2)≥n-1, then G is Hamilton connected. Corollary3.1.3Let G be a2-connected graph of order n.δ(G)≥3,H1and H2,any two non-adjacent subgraphs, are isomorphic to K2and K2respective, if d(H1)+d(H2)≥n-1, then for any two vertex u, v,{u, v}isn’t a cut set, then exit a Hamilton path between u and v.Corollary3.1.4Let G be a2-connected graph of order n.δ(G’)≥3, H1and H2,any two non-adjacent subgraphs,are isomorphic to K2, if d(H1)+d(H2)≥n-1, then for any two vertex u, v,(u, v}isn’t a cut set, then exit a Hamilton path between u and v.Theorem3.1.5Let G be a2-connected graph of order n.δ(G)≥3, Hi and H2,any two non-adjacent subgraphs,are isomorphic to P3and K2respective, if d(H1)+d(H2)≥n, then for any two vertex u, v,{u, v}isn’t a cut set, then exit a Hamilton path between u and v.Corollary3.1.6Let G be a3-connected graph of order n. H1and H2,any two non-adjacent subgraphs,are isomorphic to K2, if d{H1)+d(H2)≥n-1, then G is Hamilton connected.Corollary3.1.7Let G be a2-connected graph of order n.δ(G)≥3, H1and H2,any two non-adjacent subgraphs,are isomorphic to P3and K2respective, if d(H1)+d(H2)≥n, then for any two vertex u, v,{u, v}isn’t a cut set, then exit a Hamilton path between u and v.Theorem3.2.6Let G be a3-connected graph of order n,δ(G)≥4.H1and H2,any two non-adjacent subgraphs,are isomorphic to K3and K2, if d(H1)+d(H2)≥n, then G is Hamilton connected.Corollary3.2.7Let G be a3-connected graph of order n,δ(G)≥4. H1and H2,a.ny two non-adjacent subgraphs,are isomorphic to K3and K2, if d(H1)+d(H2)≥n, then G is Hamilton connected.Corollary3.2.8Let G be a3-connected graph of order n,δ(G)≥4. H1and H2,any two non-adjacent subgraphs,are isomorphic to K3and K2, if d(H1)+d(H2)≥ n, then G is Hamilton connected.In the forth chapter, we mainly study the properties of traceable with different conditions of degree in claw-free graphs and give the following results:Theorem4.5Let G be a2-connected claw-free graph of order n,H1and H2,any two non-adjacent subgraphs,are isomorphic to P3and K2respectively,if d(H1)+d(H2)≥n-2,then G is traceable.Corollary4.6Let G be a2-connected claw-free graph of order n,H1and H2,any two non-adjacent subgraphs,are isomorphic to K3and K2respectively,if d(H1)+d(H2)≥n-2, then G is traceable.Corollary4.7Let G be a2-connected claw-free graph of order n,H1and H2,any two non-adjacent subgraphs,are isomorphic to P3and K2respectively,if d(H1)+d(H2)≥n-2, then G is traceable. |
PDF Full Text Request