The Contractible Edges Of Spanning Tree And Perfect Matching In K-connected Graphs

Graph theory is a branch of combinatorial mathematics with a long history and a rapidly developing.It originats from an old game which is the city of Konigsberg bridge.In 1736,Euler solved this problem and published the first paper about graph theory.The structural characterizations of graph is one of the direction in graph theory research and the connectivity is a very popular topic in graph theo-ry.In the process of studying the connectivity mainly include to explore the structural characteristics and analysis of the graph.About the method of the connected graph structure,people usually use some concepts as a tool,which can keep the connectivity of the operation.A connected graph can be obtained by computation.The contractible edges and removable edges of graph is a pow-erful tool to study the structures of graph.Let e be a side in E(G),we perform the following operations on G;first,del ete the vertexs x,y and the edges adjacent to them,second,add a new vertex u and then completely connect the neighbors of x,y.The final resultant graph is denoted by G/e.If G/e is still k-connected,then the edge e is called remov-able;otherwise,e is called unremovable.This article presents the number of contractible edges of spanning tree and perfect matching in k-connected graphs.The conclusions are that:Theorem2.1 Let G be a k-connected graph and every fragment of G contains at least[k/2]vertices.H is J spanning tree G,then there are at least k+1 contractible edges of G in H.If this graph has a perfect matching,then the conclusions of contractible edges is that:Theorem 3.1 Let G be a k-connected graph and every fragment of G contains at least[k/2]+1 vertices.If this graph has a perfect matching,then there are at least[k/2]+1 contractible edges of G in M.