Path And Cycle Properties In Several Graph Families

Paths and cycles are two basic structures of graphs.In fact,many practical problems can be attributed to the problem of paths and cycles.Therefore,the research about them is very active.What is more,the famous Hamilton problem is about paths and cycles of graph in essence.After the development for dozens of years,the contents in properties of graphs' path and cycle become more and more rich and specific.The properties of path include Hamilton path(traceability), longest path,panconnectivity,path extension and so on;the properties of cycle include Hamilton cycle,longest cycle,(vertex-)pancyclicity,vertex-disjoint cycle, cycle extension and so on.However,we can not deny the fact that it is usually very difficult to study Hamilton problem in those graphs without any restriction.Then we turn to explore the graphs not containing some forbidden subgraphs such as claw-free graphs.The first motivation for studying properties of claw-free graphs apparently appeared from Beineke's characterization of line graphs.However,the main impulse that turned the attention of the graph theory community to the class of claw-free graphs was given in late 70s and early 80s.Some famous results about claw-free graphs can be seen in[1]-[3],[16]-[23].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,(K_1,4;2)-graphs,DCT graphs etc.Almost claw-free graphs are defined by Z.Ryjá(?)ek in[27].It is also a larger graph family than that of claw-free graphs.However,it is very difficult to extend many good results of claw-free graphs to almost claw-free graphs.Therefore,Yanyan Teng and Haiyan You gave the definition of strongly almost claw-free graphs:qusi-claw-free graphs[4],which contain the family of claw-free graphs and is contained in the family of almost claw-free graphs.We can call quasi-claw-free graphs,almost claw-free graphs,qusi-claw-free graphs similar claw-free graphs.Xiaoying Qu defined K_1,p-developed graphs in 2006.We devote to make the definition much better in the study of different graph family's structure.Especially, K_1,2-developed graphs contain the family of claw-free graphs and is larger than the family of claw-free graphs.We do much to study the Hamilton and path extension.We say a vertex v is a locally Connected vertex of graph G,if the neighbor of v in G is connected.In 1989,Cunqun Zhang gave the definition of quasi-locally connected graphs,after that he studied the properties of claw-free graphs and quasi-claw-free graphs in the conditions of quasi-locally connected.In 2002 Yanyan Tang and Haiyan You defined almost-locally connected graphs.The triangularly connected graph was defined by Hongjian Lai in 2004,he also gave many good results of claw-free graphs under this condition.In 2008,Mingying Liu gave the definition of H-local connected graphs on the basic of the research on many different graphs.In this paper we mainly research the properties of H-local connected qusi-claw-free graphs,which gives a good supplement to H-local connected similar claw-free graphs.This paper mainly reseaches the path and cycle's properties of K_1,p-developed graphs and qusi-claw-free graphs in diferent Conditions.In the first chapter,we give a brief introduction about some related research backgrounds and some known results.In the meantime,we also give the basic concepts,terminologies and symbols which will be used in this paper.In the second chapter,we mainly study K_1,p-deveioped graphs' property of Hamilton and path extension and give the following results:Theorem2.1.4 If a K_1,2-developed graph is connected with(?)_x,y∈V(G), (?)(x,y)≠(?),then G has a Hamilton path.Theorem2.2.7 If G is a connected,locally 2-connected K_1,2-developed graph,P isn't a Hamilton path of G,(?)_u,v∈Vp(x)(x∈V(G)-V(P)),when u,v are the developed vertex of x and u,v's pre-vertex(after-vertex),we have u^-v⁺,u⁺v^-∈E(G),then G is path extendable.In the third chapter,we discuss qusi-claw-free graphs in diferent conditions and it's cycle extension through examples and obtain the results as follows:Theorem3.1.3 Every triangularly connected qusi-claw-free graph is also quasi-locally connected qusi-claw-free graph.Corollary The order of quasi-locally connected qusi-claw-free graph's smallest vertex cut is at least 2.Theorem3.2.4 Let G be a connected,quasi-locally connected qusi-claw-free graph without net completed-claw,then G is fully cycle extendable and without net completed-claw is necessary.In the fourth chapter,we mainly obtain the results as follows:Theorem4.1.2 Every connected K_m-locally connected qusi-claw-free graph of order≥2m(m≥2) is 2-connected.Theorem4.1.4 Let G be a connected K₂-locally connected qusi-claw-free graph,for(?)_xy∈E(G),then the length of the shortest-path between any two diferent vertices of G[N(xy))]is not more than 6.Theorem4.1.6 Let Gibe a connected K₃-locally connected qusi-claw-free graph,G[{x,y,z}]is a triangle of G,then the length of the shortest path between any two diferent vertices of G[N(x,y,z))]is not more than 8.Theorem4.2.2 If G is a connected K₂-locally connected qusi-claw-free graph with |G|≥4,then G is Hamiltonian.Theorem4.3.2 If G is a connected K₂-locally connected qusi-claw-free graph withδ(G)≥3,then G is fully cycle extendable.