| The problem on paths and cycles of graphs is a very important problem ingraph theory and the research is also active. The famous Hamilton problem be-longs to the problem of paths and cycles of graphs in essence,and it is one ofthe three famous difcult problems in graph theory. What is more, Many schol-ars at home and abroad made a lot of research work on this issue. The researchresults and progress in this area can be found in literature[33]-[37]. After the de-velopment for dozens of years, the contents about the properties of path and cyclebecome more and more rich and specific. The properties of path include Hamil-ton path （traceability）,Dominating path,homogeneous-traceability, longest path,Hamilton-connected,Dominating-connected,pan-connectivity, path extendsibilityand so on; the properties of cycle include Hamilton cycle, Dominating cycle,longestcycle,（vertex-）pancyclicity, cycle extendsibility vertex-disjoint cycle,cycle-coveredand so on.However, we can not deny the fact that it is usually very difcult to studyHamilton problem in those graphs without any restriction. Then we turn to explorethe graphs not containing some forbidden subgraphs such as claw-free graphs. Thepapers which about the properties of line graph appeared in [31]-[32], and they werewritten by Seineke in1970s. Then the claw-free graphs that include line graph wasconcerned. The researh of claw-free graph was very actived in late70s and early80s.Some famous results about claw-free graphs can be seen in [15]-[30]. In addition,the definition of claw-free graph has been extended to several larger graph familiesin diferent views, such as quasi-claw-free graphs,almost claw-free graphs,etc.In this paper, we mainly discuss the relations between the degree condition（thesum degree of any non-adjacent subgraph） and properties of graphs’ paths andcycles（including Hamilton-connected,,Hamilton cycle,Dominating cycle et.）.And it gives some sufcient conditions about subgraphs’ degree of the properties of pathsand cycles in graphs and 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, wealso give some related research backgrounds and some known results.In the second chapter, we mainly study the sufcient conditions about thedegree of subgraphs of the properties of paths and cycles in claw-free graphs andgive the following results:Theorem2.1.9Let G be a2-connected claw-free graph of order n,if d（H1）+d（H2）≥n3for any two nonadjacent subgraphs H1,H2isomorphic to K1,K2,thenevery longest cycle of G is Hamilton.The bound n-3is sharp.Theorem2.2.9Let G be a2-connected claw-free graph of order n,if d（H1）+d（H2）≥n for any two nonadjacent subgraphs H1,H2isomorphic to K1,K2,thenfor each pair of vertices u, v in V （G）,if {u, v} is not cut set,then there exists aHamilton path between vertices u and v.Corollary2.2.10Let G be a3-connected claw-free graph of order n,if d（H1）+d（H2）≥n for any two nonadjacent subgraphs H1,H2isomorphic to K1,K2,then Gis Hamilton-connected.Theorem2.3.2For a2-connected claw-free graph G. If d（H1）+d（H2）+d（H3）≥|G|1,for any nonadjacent subgraphs H1, H2, H3isomorphic to K2thenevery longest cycle of G is Dominating.In the third chapter, we mainly study the sufcient conditions about the degreeof subgraphs of the properties of paths and cycles in graphs and give the followingresults:Theorem3.1.1Let G be a connected graph of order n,if d（H1）+d（H2）≥n4for any two nonadjacent subgraphs H1,H2isomorphic to K2,then every longest pathof G is Dominating.The bound n4is sharp.Theorem3.1.2Let G be a2-connected graph of order n,if d（H1）+d（H2）≥n-2for any two nonadjacent induced subgraphs H1,H2isomorphic to K3,K2,thenevery longest path of G is Dominating.Corollary3.1.3Let G be a2-connected graph of order n,if d（H1）+d（H2）≥n-2for any two nonadjacent induced subgraphs H1,H2isomorphic to K2,K2,thenevery longest path of G is Dominating.Theorem3.2.1Let G be a2-connected graph of order n,if d（H1）+d（H2）≥n-1for any two nonadjacent induced subgraphs H1,H2isomorphic to K2,K2,thenevery longest cycle of G is Dominating. Corollary3.2.2Let G be a2-connected graph of order n,if d（H1）+d（H2）≥n-1for any two nonadjacent induced subgraphs H1,H2isomorphic to K1,K2,thenevery longest cycle of G is Dominating.Theorem3.2.3Let G be a3-connected graph of order n,if d（H1）+d（H2）≥n-1for any two nonadjacent induced subgraphs H1,H2isomorphic to K3,K2,thenevery longest cycle of G is Dominating.Theorem3.3.1Let G be a2-connected graph of order n,if d（H1）+d（H2）≥nfor any two nonadjacent subgraphs H1,H2isomorphic to K2,then for each pair ofvertices u, v in V （G）,if {u, v} is not cut set,then there exists a Dominating pathbetween vertices u and v.Theorem3.3.2Let G be a2-connected graph of order n,if d（H1）+d（H2）≥n for any two nonadjacent induced subgraphs H1,H2isomorphic to K2,K2,thenfor each pair of vertices u, v in V （G）,if {u, v} is not cut set,then there exists aDominating path between vertices u and v.Corollary3.3.3Let G be a3-connected graph of order n,if d（H1）+d（H2）≥nfor any two nonadjacent subgraphs H1,H2isomorphic to K2,then G is Dominating-connected.Corollary3.3.4Let G be a3-connected graph of order n,if d（H1）+d（H2）≥nfor any two nonadjacent induced subgraphs H1,H2isomorphic to K2,K2,then G isDominating-connected.Corollary3.3.5Let G be a3-connected graph of order n,if d（H1）+d（H2）≥nfor any two nonadjacent subgraphs H1,H2isomorphic to K1,K2,then G is Dominating-connected. |
PDF Full Text Request