Hamilton连通图的一个新的充分条件  

A New Sufficient Condition for a Graph to Be Hamilton Connected

作　　者：王冬冬[1] 

机构地区：[1]淮阴工业专科学校计算机系

出　　处：《江苏师范大学学报（自然科学版）》1997年第4期8-11,共4页Journal of Jiangsu Normal University：Natural Science Edition

基　　金：国家自然科学基金

摘　　要：设Ｇ是ｎ阶３－连通无向简单图，α表示图的独立数．若对Ｇ的所有距离为２的顶点ｕ，ｖ，都有ｄ（ｕ）＋ｄ（ｖ）≥ｎ或｜Ｎ（ｕ）∩Ｎ（ｖ）｜≥α，则Ｇ是Ｈａｍｉｌｔｏｎ连通的，除非Ｇ属于一个特殊图类．Let G be a 3 connected graph of order n .If for all distinct vertices u and v,d(u,v)=2 implies d(u)+d(v)≥n or |N(u)∩N(v)|≥α, then G is Hamilton connected unless G is in a special class of graphs.Where α is the independence number of G.

关 键 词：Hamilton连通图 最长路 邻集 

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