k-树图的收缩边

The Contractible Edges of k-tree

Narayanaswamy,Sadagopan和Sunil Chandran证明了k-树图G可收缩边数目的下界为V(G)+k-2,并指出这个界是紧的.该文给出了k-树图G可收缩边数目更一般的下界,由该文的结果可以推出Narayanaswamy等人的结果,进一步证明了可收缩边数目恰好为V(G)+k-2的图的特征.

Narayanaswamy ,Sadagopan and Sunil Chandran showed that the lower bound of the number of contractible edges of k-tree G is ｜V （G）｜ ＋ k -2 and this bound is tight .In this paper ,we provide a more general lower bound for the number of contractible edges of G and the result of Naray-anaswamy ,et al .is just a corollary of our result .We characterize the graph with exactly V （G） ＋ k-2 contractible edges .