有向图为Hamilton图的一个充分条件  

A Sufficient Condition for a Digraph to Be Hamiltonian

作　　者：李瑞娟[1] 张新鸿[1] 李胜家[1] 

机构地区：[1]山西大学数学科学学院,山西太原030006

出　　处：《中北大学学报（自然科学版）》2006年第2期186-188,共3页Journal of North University of China(Natural Science Edition)

基　　金：国家自然科学基金资助项目(60174007);山西省自然科学基金资助项目(20011001);山西大学青年科技基金

摘　　要：在文献[2]中,B ang-Jensen等人猜想,如果对n阶强连通有向图D中每一对不相邻的,且具有公共内邻或公共外邻的顶点对x,y,都有它们的度和不小于2n-1,则D是H am ilton图.本文证明若对上述x,y,如果它们的度和不小于2n-1与52n-92中的最大者,则D是H am ilton图.According to the supposition by Bang-Jensen et al. , for a strong digraph D with n vertices, D is Hamiltonian if the sum of their degrees is no less than 2n-1 for every pair of non-adjacent vertices x, y with a common out-neighbor or a common in-neighbor. In this paper, the authors have proved that, if the sum of their degrees is no less than the maximum between 2n-1 and （5/2）n-9/2 for every pair of vertices with above property, D is Hamiltonian.

关 键 词：HAMILTON图 C-旁路 公共内邻 公共外邻 

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