Contractible Edge And Contractible Cycle In K Connected Graph

An edge of a k connected graph G is said to be k contractible edge, or simplycontractible edge, if its contraction results still in a k connected graph. In 1961 Tutte [1]proved that any 3 connected graph with order at least 5 has 3 contractible edges. Afterthat, the contractible edges in 3 connected graph has been studied extensively. As forthe distribution and the lower bound of contractible edges in 3 connected graph, we referthe reader to [2]. But for k≥4, Thomassen [3] showed that there are infinitely manyk connected k regular graphs, which do not have a contractible edge. A noncomplete kconnectecd graph is called contraction critical k connectecd if G has no k contractibleedge. In order to get some conditons of having a contractible edge in a k connnectedgraph, it is natural to study the contraction critical k connectecd graph. Ror k = 4,Martinov [4] completely characterized all contraction critical 4 connected graph, thatis:Theorem A There are only two special classes for 4 connected graph without4 contractible edge: the square of a cycle or the line graph of a cyclically 4 connected3 regular graph.For k≥5, it is very di?cult to give a characteration to the contraction critical kconnected graph. However, Egawa [5] proved that every contraction critical k connected(k≥4) graph has a fragment with cardinality at most k/4 . From that we know thatevery contraction critical k connected (k≥4) graph has a vertex of degree at most[5k/4] - 1. So, for 5≤k≤7, every contraction critical k connected graph contains avertex of degree k. In this direction, more results are obtained. For k = 5, Yuan [6]proved that each vertex in a contraction critical 5 connected graph is adjacent to atleast one vertex of degree 5. Later Su Jianji[7] obtained that any vertex of a contractioncritical 5 connected graph is adjacent to two vertices of degree 5. For k = 6, Yuan andSu [8] proved that:Theorem B Any contraction critical 6 connected graph has a pair of adjacentvertices of degree 6.In chapter 1, we improve Theorem B and get the following result:Theorem 1 For each vertex x of degree 6 in a contraction critical 6 connectedgraph, either there is a neighbor of degree 6 of x, or there exists a vertex y in N(x)such that there are two adjacent vertices of degree 6 in the neighborhood of y.In chapter 2, we study some forbidden subgraphs conditions to have a contractibleedge in a k connected graph. If the graph G does not have H as a subgraph, then G iscalled H - free. Thomassen [3] proved that a k connected triangle-free graph containsa k contractible edge. Egawa[9] further studied the distribution of k contractible edgesin a k connected triangle-free graph and proved that a k connected triangle-free graph...