k-连通图中最长圈上可收缩边的数目
On the number of contractible edges of longest cycles in k-connected graphs

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