k-连通图中最长圈上可收缩边的数目

On the number of contractible edges of longest cycles in k-connected graphs

给出了k-连通图中最长圈上的可收缩边的数目,得到如下结果:任意断片的阶至少为「k/2」+1的k-连通图中最长圈上至少有3条可收缩边;更进一步,若该k-连通图中存在哈密顿圈,则哈密顿圈上至少有6条可收缩边。

The number of contractible edges of longest cycles in k-connected graphs is given. The conclusions are that if every fragment of a k-connected graph has an order at least 「k /2」 ＋ 1,then there exist at least three contractible edges on the longest cycle of this graph. Furthermore,if this graph has a hamiltonian cycle,then there exist at least six contractible edges on the hamiltonian cycle.