Some Sufficient Conditions Of Strong Paths And Cycles Property In Graphs

The problem on paths and cycles of graphs is a very important problem in graph theory and the research is also active.Many practical problems can be attributed to the problem of paths and cycles.What is more,the famous Hamilton problem belongs to the problem of paths and cycles of graphs in essence.Many scholars at home and abroad made a lot of research work on this issue.The research results and progress in this area can be found in literature[38]-[42].The condition of degree and neighborhood unions becomes an important way to study the problems. In this respect,a lot of outstanding achievements have be made.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 Beincke's characterization of line graphs in[17].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 clawfree graphs can be seen in[1]-[3],[19]-[31].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 etc.In 2005. Liu Chunfang[4]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.According to this graph,I defined a new graph family -strong-[s,t]graphs,that is,there are at least t independent edges in every included subgraphs of s vertices in graph G. These graphs can be used in traffic network,communications,the configuration of computer networks,etc.In this paper,we mainly discuss the properties of graphs' path and cycle in [s,t]-graphs and the properties about degree of graphs' path and cycle in all 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,we also give some related research backgrounds and some known results.In the second chapter,we mainly study the paths and cycles of strong-[s,t] graphs and give the following results:Theorem2.1.4 If G is a strong-[4,2]graph with |G|≥6,then G is pancyclic.Theorem2.1.5 If G is a strong-[4,2]graph with |G|≥7,then G is fully cycle extendable.Theorem2.1.6 If G is a strong-[4,2]graph with |G|≥8,then G is path extendable.Theorem2.2.4 If G is a connected strong-[5,2]graph with |G|≥8,then G has a Hamilton path.Theorem2.2.5 If G is a connected,local connected strong-[5,2]graph with |G|≥8 andδ(G)≥3,then G is fully cycle extendable or G≌F.Corollary2.2.6 If G is a connected,local connected strong-[5,2]graph with |G|≥8 andδ(G)≥3,then G is fully cycle extendable.Theorem2.3.3 If G is a strong-[2m,m]graph with |G|≥3m - 1,then G has a Hamilton path. Theorem2.3.4 If G is a strong-[2m.,m]graph with |G|≥3m,then G has a Hamilton.cycle.In the third chapter,we mainly study cycles of all graphs about degree conditions and give the following results:Theorem3.8 Let G be a graph of order n≥3.If d(u)+d(v)≥n+k for every pair u,v of nonadjacent vertices.,then the every cycle C satisfying n/(k+2)＜|C|＜n is extendable.Corollary3.9 Let G be a graph of order n≥3.If d(u)+d(v)≥(3n)/2- 2 for every pair u,v of nonadjacent vertices,then G is fully cycle extendable.Theorem3.10 Let G be a graph order n≥3.If d(u)+d(v)≥n+ 1 for every pair u,v of d(u,v) = 2,then existing a vertex x∈{u,v} and each integer k with 3≤k≤n,G has a k-cycle C_k such that x∈V(C_k).In the fourth chapter,we mainly study paths of all graphs about degree conditions and give the following results:Theorem4.3 Let G be a graph of order n≥3.If d(u)+d(v)≥n+1 for every pair u,v,then G is path extendable.Theorem4.4 Let G be a graph of order n≥3.If d(u)+d(v)≥n+ 1 for every pair u,v of nonadjacent vertices,then the every path P satisfying n/3+1＜|P|＜n is extendable.