Connectivity,Union,Paths And Cycles

Paths and cycles are two basic structures of graphs. In fact, many practical problems can be attributed to the problems 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' paths and cycles become more and more rich and specific, including Hamilton path (traceability),Hamilton cycle,longest path,longest cycle,Hamilton-connected,panconnectivity,(vertex)pancyclicity,path extendability,cycle extendability and so on.In 1952 and 1960, Dirac and Ore studied the problems of paths and cycles on the condition of vertex degree , obtained respectively the famous theorems of Dirac and Ore. In 1989, Yongjin Zhu put forward the concept of implicit degree of graph . In 1987, Faudree,Gould,Jacobson, Schelp founded Neighborhood unions conditions, gave the sufficient conditions of the problems of paths and cycles from the Neighborhood . we continue to study the sufficient conditions of the problems of paths and cycles from the Neighborhood and implicit degree in the third and fourth chapter 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, we also obtain some related research backgrounds and some known results.In 2006, Xiaoyan Liu put forward the concept of s-vertices connected graph .In the second chapter, we give a general concept: (s, k)-connected graph, and obtain the following results: Theorem 2.2.1 Let G be a (s, k)-connected graph of order n , if s-k≤(?),then G is path extendable .Corollary 2.2.2 Let G be a graph of order n , if _K(G)≥(?),then G is path extendable .In the third chapter,we discuss the paths and cycles of graph on the condition of neighborhood,we mainly obtain the results as follows:Theorem 3.1.1 Let G be a 2-connected graph that G[N₂(v)] is complete graph for every vertex v in G,then G is pancyclic.Theorem 3.1.2 Let G be a 2-connected graph that G[N₂(v)] is complete graph for every vertex v in G,then G is traceable.Theorem 3.2.1 Let G be a 2-connected graph such that |N(u)∪N(v)|≥m(m is a positive number) for each pair of nonadjacent vertices u and v that are vertices of an induced claw or an induced modified claw of G, then G contains either a Hamilton cycle or a cycle of length at least m+2 .Theorem 3.2.2 Let G be a 2-connected graph of order n such that |N(u)∪N(v)|≥n-δfor each pair of nonadjacent vertices u and v that are vertices of an induced claw or an induced modified claw of G,then G is Hamiltonian.In the fourth chapter,we discuss Hamilton cycle on the condition of implicit degree,improve some corresponding results of Guohua Gu,Bing Wei , Rongzu Yu etc :Theorem 4.1.2 Let G be a 2-connected graph of order n such that d₁(u)+ d₁(v)≥(?)+δ(G) for each pair of nonadjacent vertices u and v with |N(u)∩N(v)|≤α(G) -l,then G is Hamiltonian.Theorem 4.1.5 Let G be a 2-connected quasi-claw-free graph of order n such that d₂(a)+d₂(b)≥n for each pair of nonadjacent vertices a and b in G, then G is Hamiltonian if and only if G + ab is Hamiltonian.Theorem 4.2.2 Let G be a 2-connected graph ,if there exist x,y∈S(x≠ y) such that d₂(x)+d₂(y)≥c (c is a positive number) for every independent set S={u,v,w} in G ,then G contains either a Hamilton cycle or a cycle of length at least c .