K Contractible Edges In K Connected Graphs

An edge of a k connected graph G is said to be k contractible edge, or simply contractible edge,if its contraction results still in a k connected graph. An edge that is not contractible is called a non-contractible edge. If a k connected graph has contractible edge,then we can prove some problemswhich related to connectivity of it by inductive approach. Hence, it is useful to study contractibleedge. In a k connected graph, if edge xy is contained in a triangle xyz and d(z)=k, then xy is calledtrivially non-contractible.In 1961, Tutte ([1]) proved that any 3 connected graph with order at least 5 has a contractibleedge. On the other hand, Thomassen ([2]) showed that for k≥4 there are infinitely many k-connected k regular graphs which do not have a contractible edge. In order to get some conditionsof having a contractible edge in k connected graph, the definition of contraction critical k con-nected graph have been introduced. A noncomplete k connected graph G is called contractioncritical k connected if it has no contractible edge.It is easily to see,if we deny every property of acontraction critical k connected graph, we can obtain a sufficient condition about the existence ofcontractible edge in k connected graph.We can easily prove that there are not contraction criti-cal 1 or 2 connected graphs. By Tutte's result he proved above, there are not contraction critical 3connected graphs too. The contraction critical 4 connected graphs was characterized by Fontet([3])and Martinov([4]),that is: Let G be a 4 connected graph without contractible edge, then G is eithera square of cycle or a line graph of cyclically 4 connected 3 regular graph. It is harder to charac-terize contraction critical 5 connected graphs than to characterize contraction critical 4 connectedgraphs.Up to now, there are no satisfied results about such things,let alone to characterize anygeneral contraction critical k connected graphs. Recently, it is important to study the property ofcontraction critical k connected graphs,then,come out some sufficient conditions about the existenceof contractible edge in a k connected graph.In 1981, Thomassen([2]) proved the following result.Theorem A Let G be a k connected graph with no contractible edges. Then G contains atriangle, i. e., K₃.In other words, let G be a k connected graph with no triangles, then G contains a contractibleedge. Egawa et al.([5]) counted the humble of contractible edges in a k connected graph with notriangles,he proved that:Theorem B Let G be a k connected graph with no triangles. Then G contains min{|V(G)|+2/3k²-3k,|E(G)|}k-contractible edges. As Theorem B show, k connected graph G without triangle have considerablecontractible edge. Hence the condition 'without triangle' is too strong, Egawa([6]) studied theminimum degree condition for a k connected graph to have a contractible edge and proved thefollowing theorem,that is:Theorem C Let k≥2 be an integer, and let G be a k connected graph withδ(G)≥[5k/4].Then G has a contractible edge, unless 2≤k≤3 and G is isomorphic to K_k+1.If the graph G does not have a subgraph which is isomorphic to a given graph H, then Gis called H-free. Let K₄^- denote the graph from K₄ by deleting just one edge. Kawarabayashi([7])proved the following result.Theorem D Let k≥3 be an odd integer, and let G be a K₄^--free k-connected graph.ThenG has a contractible edge.LiXiangdun et. al([8]) further studied the K₄^--free k-connected graphs, and obtained a lowbound about the humble of contractible edges in such graphs:Theorem E Let k≥5 be an odd integer, and let G be a K₄^--free k connected graph.ThenG has at least k+1 contractible edges.Triangle plays an important role in the study of contractible edge.Mader([9]) proved thatthere exist many triangles in contraction critical k-connected graphs.He obtained the followingresult.Theorem F Let G be a contraction critical k connected graph.then G contains at least|V(G)|/3 triangles.Recently, Kriesell ([10]) further improved Mager's result to that a contraction critical kconnected graph G contains at least 2|V(G)|/3 triangles.A bowtie is the graph consisting of two triangles with exactly one vertex in common.Recently,Ango et.al([11]) obtained the following result.Theorem G Let k be an integer,k≥4.If a k connected graph G has no contractible edge,then G contains a bowtie.In other words, let G be a k (k≥4) connected graph with no bowtie,then G contains acontractible edge.By carefully studied the bowtie-free k connected graphs,we obtained the following results inchapter 1.Theorem 1 Let G be a k connected graph with no bowtie as its subgraph,and with no Has its induced subgraph.Then G contains at least k contractible edges.(k≥4).(The given graph H=kK₁+K₂-{uy, vx}+{xy}, where K₂=uv, x, y∈V(k/K₁). That is,H contains a 4-cycle and the cycle has exactly one edge in k-2 triangles.)We constructed a 4 regular 4 connected graph to see that our lower bound k is a good one.Theorem 2 Let G be a k connected graph with no bowtie and with no (k-2)K₁+K₂ asits subgraph.Then G contains at least 2k contractible edges.(k≥4). In chapter 2, we study some forbidden subgraphs conditions to have a contractible edge in aminimally k connected graph.A k(k≥2) connected graph G is said to be minimally k connected if G-e is no longer kconnected for any e∈E(G). If G is not minimally k connected, we may delete some edges withkeeping the connectivity of G until G is minimally k connected. Hence, every k connected graphhas a minimally k connected subgraph. Obviously, if G is H-free, then every subgraph of G is alsoH-free.On the other hand, if a k connected subgraph of graph G does have a k contractible edge e,then e is also a k contractible edge in G. Hence, it is possible to obtain some forbidden subgraphconditions for the existence of a k contractible edge by studying the minimally k connected graph.Ando et.al in[12] obtained the following result, that is:Theorem H Let G be a minimally k (k≥5) connected graph which dose not contain aK₁+C₄. If for any vertex x∈V(G) of degree k, there exists one edge incident with x which is notcontained in any triangle, then G has a k contractible edge.For the contractible edge in a minimally k connected graph, QiEnfeng et.al([13]) proved that,when k≥8, if k connected graph G has no P=K₁+2P₃ as its subgraph, and if for any vertexx∈V(G) of degree k, there exists an edge incident with x which is not contained in any triangle,then G has a k contractible edge.By carefully studied the K₁+C₄, we can easily find that the K₁+C₄ is just the P₃+2K₁. Inchapter 2,we obtained the following result.Theorem 3 Let G be a minimally k(k≥5) connected graph with no P₃+3K₁. If for anyvertex x∈V(G) of degree k, there is an edge of E(x) which is not contained in any triangle,thenG has a k contractible edge.We constructed a 5-regular 5-connected graph which has K₁+C₄ as its subgraph, but has noP₃+3K₁ as its subgraph, and for any vertex of degree 5, there is an edge incident with it whichis not contained in any triangle. Clearly, the graph meets the conditions of theorem 3,but does notmeet the conditions of theorem H. We can easily find, G contains several contractible edges.Fromthe example, we can see that the conditions of theorem 3 is better than the conditions of theoremH to confine the existence of a contractible edge in a graph. By theorem 3, we naturelly want togeneralize it. We obtained the following result.Theorem 4 Let G be a minimally k connected graph with no P₃+tK₁, and for any vertexx∈V(G) of degree k, there is an edge of E(x) which is not contained in any triangle. Whenk≥4t-1. Then G contains a k contractible edge. (t≥4).