Contractable Edge Of Connected Graph

Edge contraction is a common operation in graph theory.Let G be a k-connected graph,e is an edge of G.If G/e is again a k-connected graph then we say e is an k-contractible edge of G.A k-connected graph without k-contractible edge is called a contraction critical k-connected graph.People have done a lot of research on the exis-tence conditions and the distribution of k-contractible edges,and has achieved a lot of results.Let G be a(k-1)-connected graph.If for every(k-1)-separator T,G-T has one component which contains exactly one vertex,then we call G a quasi-k-connected graph.Further,if G is quasi-k-connected graph and every(k-1)-separator of G contains no edge,then we call G a strong quasi-k-connected graph.In this paper,we give the definitions of quasi-k-contractible edge and that of strong quasi-k-contractible edge,which are the generalizations of k-contractible edge.Further,we study on the existence conditions and the distribution of quasi-k-contractible edge and strong quasi-k-contractible edges,respectively.The main results are as follows:(1).Let G be a contraction critical 4-connected graph,then G(?)Km is a contraction critical quasi-4m-connected graph.(2).Let k≥5,and let G be a K4--free k-connected graph,then the graph induced by the set of all quasi-k-contractible edges is a 2-connected spanning subgraph of G.(3).Let G be a 5-connected graph,then G has an edge e such that G/e is quasi-5-connected.(4).For a strong quasi-4-connected graph,we focus on the local structure of vertex of degree 3.It is shown that there are only possible three configurations around x if x incident to at least two non-strong quasi-4-connected edges.Moreover,it is shown that there is exactly one configuration around x if x incident to 3 non-strong quasi-4-connected edges.(5).For a strong quasi 4-connected graph G which dose not contains two special graphs as subgraph,it is shown that G has at least 1/2|V(G)| strong quasi-4-contractible edges.Further,the structure of a special of strong quasi-4-connected graph which has exactly 1/2|V(G)|strong quasi-4-contractible edges are characterized.Moreover we give a way of how to constructs such a graph.(6).For a minimal 4-connected graph G,we show that there is a contractible edge with distance at most one from an edge e=xy if both end vertices of e have degree at least 5.