k-连通图中生成树和完美匹配上的可收缩边

The contractible edges of a spanning tree and a perfect matching in k-connected graphs

给出了k-连通图生成树和完美匹配上的可收缩边数目,得到如下结果:任意断片的阶都大于「k/2■的k-连通图中生成树上至少有4条可收缩边;若该k-连通图中存在完美匹配,则完美匹配上至少有「k/2■+1条可收缩边。

The numbers of contractible edges of a spanning tree and a perfect matching in k-connected graphs are given.The conclusions are that if every fragment of a k-connected graph has an order more than「k/2■,then there exist at least four contractible edges on the spanning tree of this graph. Furthermore,if this graph has a perfect matching,then there exist at least 「k/2■ + 1 contractible edges on the perfect matching.