The Properties Of Paths And Cycles With Degree Of Subgraph In Several Graph Families

The problem on paths and cycles of graphs has always been an active area ofresearch. Paths and cycles are two basic structures of graphs, meanwhile, they arealso efective tools to analyze graphs. The results and advances in this aspect canbe found in the literatures [34]-[38]. What is more, the famous Hamilton problemis about paths and cycles of graph in essence. After the development for dozensof years, the contents in properties of graphs’path and cycle become more andmore rich. The properties of path include traceability, longest path, Hamilton-connected, panconnectivity, path extendsibility and so on; the properties of cycleinclude Hamilton cycle, Dominating cycle, longest cycle, vertex-pancyclicity, cycleextendsibility 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 ex-plore the graphs ont containing some forbidden subgraphs such as claw-free graphs.The first motivation for studying properties of claw-free graphs apparently appearedfrom Beineke’s characterization of line graphs in [17]-[18]. However, the main im-pulse that turned the attention of the graph theory community to the class ofclaw-free graphs was given in late70s and early80s. Some famous results aboutclaw-free graphs can be seen in [2]-[4],[19]-[34]. The definition of claw-free graph has been extended to several larger graphfamilies in diferent views, such as quasi-claw-free graphs, almost claw-free graphsand so on. Among them, some research progress of quasi-claw-free graphs can befound in [35]-[37].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 traceable,Hamilton, cycle Hamilton connected, et.). And it givessome sufcient conditions of properties of graphs’ paths and cycles in claw-freegraphs 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, 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 claw-free graphs and give the following results:Theorem2.1.3Let G be a connected claw-free graph of order n. H1and H2,any two non-adjacent induced subgraphs, are isomorphic to K1and P3respectively,if d(H1)+d(H2)≥n2, then G is traceable.Theorem2.2.6Let G be a two-connected claw-free graph of order n. H1andH2, any two non-adjacent subgraphs, are isomorphic to K2, if d(H1)+d(H2)≥n2,then G contains Hamilton cycle.Corollary2.2.7Let G be a two-connected claw-free graph of order n. ifδ(G: Kn2)≥21, then G contains Hamilton cycle.Theorem2.3.3Let G be a three-connected claw-free graph of order n, H1andH2, any two non-adjacent subgraphs, are isomorphic to K2, if d(H1)+d(H2)≥n,then G is Hamilton connected.Corollary2.3.4Let G be a three-connected claw-free graph of order n, H1and H2, if δ(G: Kn2)≥2, then G is Hamilton connected. Theorem2.4Let G be a four-connected claw-free graph of order n, H1andH2, any two non-adjacent subgraphs, are isomorphic to K3and K2respectively. ifd(H1)+d(H2)≥n, then there exists a dominant path between any two vertexes ofG.In the third chapter, we mainly study the traceability with K2in quasi-claw-free graphs and give the following results:Theorem3.4Let G be a two-connected quasi-claw-free graph of order n. H1and H2, any two non-adjacent subgraphs, are isomorphic to K2, if d(H1)+d(H2)≥n1, then G is traceable.Corollary3.5Let G be a two-connected quasi-claw-free graph of order n. ifδ(G: K2)≥n12, then G is traceable.