Paths And Cycles InSeveral Special 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. The research result and progress in this area can be found in literature[15]-[18]. 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 extendsibility and'so on; the properties of cycle include Hamilton cycle, longest cycle, (vertex-)pancyclicity, vertex-disjoint cycle, cycle extendsibility 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 characteriza-tion of line graphs in [19]-[20]. 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 [30]-[47]. 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, (K1,4;2)-graphs, DCT graphs etc. Also, there are a lot of good results about path factor in [9]-[14].Some famous results about k - walk can be seen in [21]-[26]. Liu Chunfang [2] defined a new graph family-[s,t]-graphs, that is, there are at least t edges in every included subgraphs of s vertices in graph G. [s,t]-graphs can be used in traffic network, communications, the configuration of computer networks, etc. Cheng Jianmin[48]defined a new graph family-strong-[s,t]-graphs based on [s,t]-graphs, that is,there are at least t independent edges in every included subgraphs of s vertices in graph G. In this paper, we mainly discuss the properties of graphs' path and cycle in [s,t]-graphs and strong-[s,t]-graphs.In the first chapter, we give a brief introduction about the basic concepts, termi- nologies and symbols which will be used in this paper.In the meantime,we also give some related research backgrounds and some known results.In the second chapter,we mainly study the traceability ofδ≥k+1,k-connected [k+4,3]-graph and obtain the result as follows:Theorem 2.7 If G is aδ≥k+1,k-connected[k+4,3]-graph,then G has a Hamilton path or G≌(?)k+3VGk+1.Corollary 2.8 If G is aδ≥k+1,k-connected[k+4,3]-graph and |G|≥2k+5,then G has a Hamilton path.In the third chapter,we mainly study the longest path of connected[5,2]-graph and the shortest walk of connected[5,3]-graph,obt ain the result as follows:Theorem 3.1.5 If G is a connected[5,2]-graph and |G|≥6,there are a positive integer t(t≤[n/3]),such that the longest path of G at least is n-t.Moreover [n/3]is,best possible.Theorem 3.2.5 Let G be a k-connected[5,3]-graph,then(1)G has a 2-walk.(2)For any x∈V (G)there is a 2- walk C such that u(x,C)=lif and only if x is not a cutvertex of G.(3)If n≥8 andis connected then there is a shortest 2-walk C such that v(x,C)=1.In the fourth chapter,we mainly study the path factor of two special graph family and give the following results:Theorem4.1.5 If G is a connected[4,2]-graph andδ(G)≥d,then G has a path-factor satisfying the rank of every path no less than d+1.Theorem4.2.4 If G is a connected[4,2]-graph,let |V(G)|=n=∑ik=1ai,with ai≤7,1≤i≤k,and suppose thatσ2(G)≥n+k-1.It is proved that for any k vertices v1,v2,...vk in G,there exist vertex-disjoint paths P1,P2,…Pk such that |V(Pi)|=ai and vi is a endvertex of Pi for 1≤i≤k.