广西师范学院学报（自然科学版）
廣西師範學院學報（自然科學版）
엄서사범학원학보（자연과학판）
JOURNAL OF GUANGXI TEACHERS EDUCATION UNIVERSITY(NATURAL SCIENCE EDITION)
2014年
2期
10-13,28
,共5页
k-树%连通度%收缩边
k-樹%連通度%收縮邊
k-수%련통도%수축변
k-tree%connectivity%contractible edge
Narayanaswamy ，Sadagopan和Sunil Chandran证明了k-树图G可收缩边数目的下界为V（G）＋ k -2，并指出这个界是紧的。该文给出了 k-树图G可收缩边数目更一般的下界，由该文的结果可以推出Narayanaswamy等人的结果，进一步证明了可收缩边数目恰好为V （G ）＋ k -2的图的特征。
Narayanaswamy ，Sadagopan和Sunil Chandran證明瞭k-樹圖G可收縮邊數目的下界為V（G）＋ k -2，併指齣這箇界是緊的。該文給齣瞭 k-樹圖G可收縮邊數目更一般的下界，由該文的結果可以推齣Narayanaswamy等人的結果，進一步證明瞭可收縮邊數目恰好為V （G ）＋ k -2的圖的特徵。
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 .
