| The problem on paths and cycles of graphs is a very important problem in graphtheory and the research is also active. Many practical problems can be attributedto the problem of paths and cycles.The famous Hamilton problem belongs to theproblem of paths and cycles of graphs in essence,and it is one of the three famous dif-ficult problems in graph theory. What is more, Many scholars at home and abroadmade a lot of research work on this issue. The research results and progress inthis area can be found in literature[31]-[35]. The condition of degree, neighborhoodsum and neighborhood unions becomes an important way to study the problems.In this respect, a lot of outstanding achievements have be made. After the devel-opment 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）,homogeneous-traceability, longest path, Hamilton-connected,pan-connectivity, path extendsibility and so on; the properties of cycle includeHamilton cycle, Dominating-cycle,longest cycle,（vertex-）pancyclicity, cycle extend-sibility vertex-disjoint cycle,cycle-covered and 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 [29]-[30], and they were written 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 [13]-[28]. 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 and cy-cles（including Hamilton connected, traceable,Hamilton cycle et.）.And it gives somesufcient conditions about the properties of paths and cycles in graphs and claw-freegraphs.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 properties of paths and cycles withdiferent conditions of degree in graphs and claw-free graphs and give the followingresults:Theorem2.1.3Let G be a2-connected of order n,H1,H2, any two non-adjacent subgraphs,are isomorphic to K2,if d（H1）+d（H2）≥n-2,thenG containsDominating cycle.Corollary2.1.4Let G be a2-connected of order n,H,a subgraph in G,isisomorphic to K2,we have d（H）≥（n-2）/2,then G has a Dominating cycle.Theorem2.2.4Let G be a two-connected claw-free graph of order n.H1and H2,any two non-adjacent subgraphs,are isomorphic to P3and K2respectively,ifd（H1）+d（H2）≥n2,then G contains Hamilton cycle.Theorem2.3.1Let G be a three-connected claw-free graph of order n,H1and H2,any two non-adjacent subgraphs,are isomorphic to K3and K1respectively,ifd（H1）+d（H2）≥n3,then G contains Hamilton cycle. In the third chapter, we mainly study the properties of Hamilton-connectedwith diferent conditions of degree in claw-free graphs and give the following results:Theorem3.5Let G be a two-connected graph of order n.H1and H2,any twonon-adjacent subgraphs,are isomorphic to P3and K1respectively,if d（H1）+d（H2）≥n,then G is Hamilton-connected.In the forth chapter, we mainly study the properties of traceabled with diferentconditions of degree in quasi-claw-free graphs and give the following results:Theorem4.4Let G be a2-connected quasi-claw-free graph of order n,H1and H2,any two non-adjacent subgraphs,are isomorphic to K3and K1respectively,ifd（H1）+d（H2）≥n1,then G is traceable. |
PDF Full Text Request