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

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

作　　者：王珊珊[1] 齐恩凤[1] 

机构地区：[1]山东大学数学学院,山东济南250100

出　　处：《山东大学学报（理学版）》2015年第10期27-31,共5页Journal of Shandong University(Natural Science)

基　　金：国家自然科学基金资助项目(11471193)

摘　　要：给出了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.

关 键 词：K-连通图 可收缩边 最长圈 哈密顿圈 

分 类 号：O157[理学—数学]