k-树图的收缩边

作者：黄乐贤; 覃城阜

来源：广西师范学院学报(自然科学版), 2014, (2): 10-13,28.

DOI：10.3969/j.issn.1002-8743.2014.02.003

• k-树
• 连通度
• 收缩边

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

• 出版日期2014
• 单位南宁师范大学