On The Number Of Contractible Edges Of Longest Cycles In K-connected Graphs

The connectivity is one of the basic properties of the graph. Research on structural characterizations of graph is a very popular topics in graph theo-ry. The concept of contractible edges is a powerful tool to study the structure of graphs and to prove properties of graphs by inductionThis article presents the number of contractible edges on the longest ccles in k-connected graphs. The conclusions are as following:Lemma 2.1 Let G be a k-connected graph,and P the longest (x, y) -path of G such that xixi+1(i=1,2,...,n - 1) is a non-contractible edge of P and S={xi,xi+1,u1...uk-2}is a k-vertex cut.Then each connected component of G/S contains at least a point of P.Lemma 2.1 Let G be a k-connected graph,and P the longest (x, y)-path of G.If every fragment of G contains at least[k/2]+1 vertices,then there are at least two contractible edges on P.Theorem 3.1 Let G be a k-connected graph and every fragment of G contains at least [k/2]+1 vertices.If C= x1x2…xnx1 is the longest cycle of G,then there are at least two contractible edges on C.Furthermore, if the graph has a hamiltonian cycle,then the following con-clusion is true:Theorem 3.2 Let G be a k-connected graph and every fragment of G contains at least[k/2]+1 vertices.If G contains a hamiltonian cycle C1,then there are at least six contractible edges on C1.