Study On Path,Cycle And Connectivity Properties Of Graphs

Graph theory is one of the important branches in a modern mathematics. The problem on paths and cycles of graphs is a very important sub jet in graph theory and the research is also active. Many practical problems can be attributed to the problem of paths and cycles.The research results and progress in this area can be found in literature.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 in. 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.In 2005,Liu Chunfang,Wang Jianglu [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. The "α(G)≤ k if and only if G is a [k+1,1]-graph (where a(G)is the independent number of graph G)".So in a sense, [s,t]-graph is generalization concept of independent number. A lot of problems can be attributed to the study of [s, t]-graphs. For example, in the coloring, traffic network, communication system, com-puter network configuration and so onAt present, the research on [s, t]-graphs are concentrated in the study of the paths, cycles properties, the existing [s,t]-graphs results are mostly s, t is a small positive integer.The first general results is the two was given in Mou Lei,Wang Jianglu [3]:(1) Let G be a k-connected, [k+2,2]-graph(k≥ 2),then G has Hamilton cycle or G is isomorphic to P Petersen graph or Kk+i V Gk-(Where Gk is any graph with k vertices,the same as below)(2) Let G be a k-connected, [k+3,2]-graph(fc≥2),then G has Hamilton path or G is isomorphic to Kk+2∨ GkAccording to independent number α(G) and connectivity k(G) Chvatal-Erdos and Bondy gave the following classical results,which can be derived by these two results.(a) (Chvatal-Erdos and Bondy [6]) Let G be a graph of order n(n≥ 3),α(G≤ k(G), then G has Hamilton cycle.(b) (Bondy [7]) Let G be a graph of order n(n≥ 3),a(G)≤ k(G)+1, then G has Hamilton path.In [6],Chvatal-Erdos also gave another classical result:Theorem Let G be a graph of order n(n≥3),α(G≤ k(G)-1, then G is Hamilton-connected.In the second chapter we will give its generalization:Theorem Let G be a k-connected, [k+1,2]-graph,then G either is Hamilton-connected or G is isomorphic to Kk∨ GkIn view of the present research on [s,t]-graph is still at primary stage, this paper continues to study path and cycle properties of [s,t]-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 properties of Hamilton-connected and give the following results:Theorem 2.1.1 Let G be a k-connected,[k+1,2]-graph(k≥ 2),then G either is Hamilton-connected or G is isomorphic to Kk∨Gk-Corollary 2.1.1 Let G be a k-connected, [k+1,2]-graph and|G|≥2k+1 ,then G is Hamilton-connected.Corollary 2.1.2 Let G be a δ≥ k+1,k-connected, [k+1,2]-graph,then G is Hamilton-connected.Corollary 2.1.3 Let G be a α(G)≤ k-lgraph,then G is Hamilton-connected.Theorem 2.1.2 Let G be a δ≥ k+1,k-connected, [k+2,3]-graph(k≥2),then G either is Hamilton-connected or G is isomorphic to Kk+i VCorollary 2.1.4 Let G be a δ≥k+1,k-connected, [k+2,3]-graph and|G|≥ 2k+3,then G is Hamilton-connected.Corollary 2.1.5 Let G be a δ> k+2,k-connected, [k+2,3]-graph,then G is Hamilton-connected.In the third chapter, we mainly study the properties of paths and cycles in [s,t]-graphs and give the following results:Theorem 3.1.1 Let G be a [k+3,2]-graph(k≥2) and does not contain Hamilton path, P is one of the longest path in G,any branch of G-V(P) suppose B meet |NP(B)|≥k, then G is isomorphic to Kk+2∨Gk.Corollary 3.1.1 Let G be a k-connected, [k+3,2]-graph,then G either contains Hamilton path or G is isomorphic to Kk+2 V Gk-Theorem 3.1.2 Let G be a δ≥k+1,[k+4,3]-graph(k≥2) and does not contain Hamilton path, P is one of the longest path in G,any branch of G—V(P) suppose B meet|Np(B)|≥ k, then G is isomorphic to Kk+3∨Gk+1Corollary 3.1.2 Let G be a δ≥ k+1, k-connected [k+4,3]-graph,then G either contains Hamilton path or G is isomorphic to Kk+3∨Gk+1Theorem 3.1.3 Let G be a [k+2,2]-graph(k≥ 2) and does not contain Hamilton cycle,C is one of the longest cycle in G,any branch of G-V(C) suppose B meet |NC(B)|≥ k, then G is isomorphic to Petersen graph or to Kk+1∨GkCorollary 3.1.3 Let G be a k-connected [k+2,2]-graph,then G either contains Hamilton cycle or G is isomorphic to Petersen graph or to Kk+1∨GkTheorem 3.1.4 Let G be a [k-1,2]-graph(k≥2) and is not a Hamilton connected, P is one of the longest path in G,any branch of G-V(P) suppose B meet|NP(B)|≥k, then G is isomorphic to Kk V∨GKTheorem 3.1.5 Let G be a [k+2,3]-graph(k≥ 2) and is not a Hamilton connected, P is one of the longest path in G,any branch of G-V(P) suppose B meet|NP(B)|≥ k, then G is isomorphic to Kk+1∨Gk+1Theorem 3.2.1 Let G be a δ(G)≥ 3,[4,2]- graph,C is one of the longest cycle in G,any branch of G-V(C) suppose B meet|NC(B)|≥ 1,then G has 2-factor.Corollary 3.2.1 Let G be a connected-graph,if δ(G)≥ 3,then G has 2-factor.Theorem 3.2.2 Let G be a [k+2,1]-graph(k≥2) of order n(n≥C is one of the longest cycle in G,any branch of G-V(C) suppose B meet|NC(B)|≥ k, then G has 2-factor.Corollary 3.2.2 Let G be a k-connected [k+2,1]-graph(k≥ 2) of order n(n≥5),then G has 2-factor.In the forth chapter, we mainly study the properties of Dominating paths and cycles [s, t]-graphs and give the following results:Theorem 4.1.1 Let G be a k-connected, [k+3,3](k≥2) graph,then contains Dominating cycle.Theorem 4.2.1 Let G be a k-connected, [k+4,3](k≥2) graph,then contains Dominating path.