The Contractible Edges Of K-tree

The theory of graph connectivity is a corner stone of graph theory; its method and technics of is widely used in graph theory. Its progress always make the whole graph theory step forward. The k-contractible edges play a key role in the study of graph connectivity, especially it is powerful in a inductive proof. A k-tree is a special k-connected graph; it possess many interesting combinatorial properties. For many NP-complete problems there are polynomial time algorithms on k-trees for a fixed value of k. In this paper, based on the papers [2,7], we defines a new graph T(G), which is corresponding to the k-tree graph G, Simplical vertex S(G) and the RP-operation and so on. We research properties of T(G) and S(G), and then we use them to characterize the structure of Gc, which is the graph induced by the contractible edge of k-tree graph. We give the new lower bond of the number of contractible edges in k-tree and we completely characterize the connectivity of Gc-The following is the main results of the paper.1. The number of contractible edges of k-tree G.This paper introduced a new parameter T(G) for k-tvees G, receive the more generally lower bound of the number of contractible edges and the scope of the number of unretractive edges of k-tree G, and can fully describe the struc-ture characteristics of the contractible edge number to |G|+k-2 of k-tvee G. By studying the distance between any two points the of TiG), shows that the distance between two points of G.2. On the connectivity of graph induced by the contractible of k-tree graph.We introduced the concept of Simplical vertex set S(G), we show that k(Gc)= S(Gc) and, for 3< S(Gc)< k, Gc is super-connected.3. The structure characteristics of T(G) induced by k-tree graph.We introduced the RP-operations, Gc is/c-regular if G can be constructs from two special k-trees by series of RP-operations.