Paths And Cycles In H-locally Connected Graphs

Paths and cycles are two basic structures of graphs. In fact, many practicalproblems can be attributed to the problem of paths and cycles. Therefore, theresearch about them is very active. 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 and specific. The properties of path include Hamilton path (traceability),longest path, panconnectivity, path extensibility and so on; the properties of cycleinclude Hamilton cycle, longest cycle, (vertex-)pancyclicity, vertex-disjoint cycle,cycle extensibility and so on.However, we can not deny the fact that it is usually very di-cult 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. Thefirst motivation for studying properties of claw-free graphs apparently appeared fromBeineke's characterization of line graphs in [17]-[18]. However, the main impulse thatturned the attention of the graph theory community to the class of claw-free graphswas given in late 70s and early 80s. Some famous results about claw-free graphscan be seen in [2]-[4], [19]-[34]. In addition, the definition of claw-free graph hasbeen extended to several larger graph families in di-erent views, such as quasi-claw-free graphs, almost claw-free graphs, (K_1,4;2)-graphs, DCT graphs etc.A.Ainouche[7] defined a new graph family-quasi-claw-free graphs and he also given several re-sults about paths and cycles in the new graph family.After that,many researchershave done a lot of work to study Hamilton problem in quasi-claw-free graphs[35]-[37].Almost claw -free graphs are defined by Z.Ryj a br′evecek in [38].It is also a largergraph family than that of claw-free graphs.However,it is very di-cult to extend manygood results of claw-free graphs to almost claw-free graphs.Therefore,Yanyan Tengand Haiyan You gave the definition of strongly almost claw-free graphs[5],which contain the family of claw-free graphs and is contained in the family of almost claw-free graphs. However,many good results of claw-free graphs that have not beenextended to almost claw-free graphs can be extended to strongly almost claw-freegraphs successfully.We say a vertex v is a locally connected vertex of graph G,if the neighbor ofv in G is connected.In 1989,CunZuan Zhang gave the definition of quasi-connectedgraphs,after that he studied the properties of claw-free graphs and quasi-claw-freegraphs in the conditions of quasi-locally connected.In 2002 Yanyan Teng and Haiyan defined almost locally connected graphs. The triangularly connected graphwas defined by HongJian Lai in 2004,he also gave many good results of claw-freegraphs under this condition.XiaoYing Qu has extended these results to quasi-claw-free graphs and strongly almost claw-free graphs.In the latter years many relateddefinitions such as 2-order neighbor connected ,NC-local connect and so on.Thedefinition of the H-local connected graph was gave on the basic of the research onmany di-erent graphs.In 1997,Zdenek,Ryjacek defined the concept of closure ,and gave many goodresults of the Hamilton problem.This closure mainly increases edges in the neighborof the locally connected vertexes.Latter,H.J.Broersma and Trommel defined theK4-closure and K4-closure,Roman C-ada defined the C4-closure and C5-closure.Thesemotivated we to define the K₂-closure and K₂-closure. In this paper we mainly re-search the paths and cycles of claw-free graphs and quasi-claw-free graphs in the con-dition of K₂-local connection,and some properties of K₂-closure and K₂-closureof claw-free graphs and quasi-claw-free graphs,which we defined in this paper.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 thy properties of H-locally connectedgraphs and give the following results:Theorem2.1 If G is a connected K₂-locally connected graph, then G is 2-connected or G (?) P₃(K_1,2).Theorem2.2 Every connected Km-locally connected claw-free graph of order≥2m(m≥2)is 2-connected. Theorem2.3 Let G be a connected K₂-locally connected claw-free graph,andfor -xy∈E(G),P = x₁x₂ ...x_k is the shortest path between any two di-erentvertexes,then k≤6.Theorem2.4 Let G be a connected K₃-locally connected claw-free graph.G[{x,y,z}] is a of G,then the length of the shortest path between any two dif-ferent vertexes of G[N(x,y,z)] is not more than 7.In the third chapter, we mainly extend the result of the third chapter.Theorem3.1.6 If G is a connected, K₂-locally connected claw-free graph with|G|≥4, then G is Hamiltonian.Theorem3.2.3 If G is a connected, K₂-locally connected claw-free graph withδ(G)≥3, then G is fully cycle extendable.In the forth chapter, we give the following results about K₂-closure andK₂-closure.Theorem 4.2.3 Let G be a claw-free graph and let xy be an eligible edgeof G.Let Gxy be a K₂-local completion of G at xy.Then the graph Gxy is still aclaw-free graph.Corollary 4.2.4 If G is a claw-free graph,then the K₂-closure of G is aclaw-free graph.Theorem 4.2.5 Let G be a quasi-claw-free graph and let xy be an eligibleedge of G.Let Gxy be a K₂-local completion of G at xy .Then the graph Gxy is stilla quasi-claw-free graph.Corollary 4.2.6 If G is a quasi-claw-free graph,then the K₂-closure of G isa quasi-claw-free graph.Theorem 4.3.1 Let G be a claw-free graph and let xy be an eligible edgeof G.Let G_xy' be a K_'2-local completion of G atxy .Then the graph G_xy' is still aclaw-free graph.Corollary 4.3.2 If G is a claw-free graph,then the K₂-closure of G is aclaw-free graph.Theorem 4.3.3 Let G be a quasi-claw-free graph and letxy be an eligibleedge of G.Let Gxy be a K₂-local completion of G at xy .Then the graph Gxy is still a quasi-claw-free graph.Corollary 4.3.4 If G is a quasi-claw-free graph,then the K₂'-closure of G isstill a quasi-claw-free graph.Theorem 4.3.5 Let G be a graph,then K₂' (G) is well defined.In the last chapter,we give the following result about the property of cycleextendable in K_1,4;2-graph.Theorem 5.5 Let G be a connected almost locally connected K_1,4;2 graphwith independent centers of induced clawK(1,3) is fully cycle extendable.