Splitting And Contractible Edges In6-connected Graphs

For a k-connected graph G and an edge e of the graph G, we denote by G/e the graph abtained from graph G by contraction of the edge e. If G/e is also k-connected, then edge e is said to be a k-contractible edge, and contractible edge for short, otherwise known as the non-contractible edge. Since contraction of a k-connected edge in a k-connected graph can be used to prove some properties for inductive arguments, the distribution of k-contraetible edges can be meaningful. If the edge xy in a triangle xyz, and d(z)=k, it is easy to see that the edge xy is not a contractible edge, which is known as the trivial non-contractiblc edges.In the paper, the splitting operation at a vertex of degree six in a6-connected graph is defined.Definition:let G be a6-connected graph and let x be a vertex of G of degree six. Let NG(x)={x1, x2, x3, x4, x5, x6}.Then we consider the following operation.(1) delete the vertex x,(2) add the edge x1x2if x1and x2are not already joined by an edge, and(3) add the edge x3x4if x3and x4are not already joined by an edge, and(4) add the edge x5xi if x5and xi are not already joined by an edge, i=1,2,3,4, and(5) add the edge x6xj if x6and xj are not already joined by an edge,3=1.2,3,4.5. We call this operation splitting at x, and denote the resulting graph by Gx1,x2,x3x4x.In other words, Gx1x2,x3x4x is the graph defined by V(Gx1x2,x3x4x)＝V(G)-{x}, E(Gx1x2,x3x4x)=E(G-x)∪{x1x2,x3x4,x5x6,xix5,xix6:i=1.2.3,4}.We consider splitting and contractible edges as tools for reduction of6-connected graphs. We prove the following theorem.Theorem:For a6-connected graph G of order at least eight, if the order of any end in graph G is not equal to two, and for any vertex z of degree6, G[NG(z)] contains a subgraph (K2∪2K1)+K2, then, for any x in V(G), one of the followings holds:(1) A6-contractible edge is incident with x:(2) There exists a vertex y of degree six in NG(x) such that a6-contractible edge is incident with y;(3) There exists a vertex y of degree six in NG(x) such that after some splitting at vertex y in graph G, and the resulting graph is also6-connected.