一类K_(1,3)-free Hamiltonian图  

A K_(1,3)-free Hamiltonian Graphs

作　　者：赵克文[1] 陈德钦[2] 

机构地区：[1]琼州大学信息科学与数学研究所,海南五指山市572200 [2]琼州大学数学系,海南三亚市572022

出　　处：《计算机科学》2007年第8期227-228,247,共3页Computer Science

基　　金：海南省自然科学基金资助项目(批准号10501)

摘　　要：1988年在美国Kalamazoo召开的"第六届国际图论、组合及其应用会议"上提出无爪图猜想:若3连通n≥3阶K1,3-free图G的不相邻的任两点x、y均有|N(x)∪(N(y)|≥(2n-6)/3,则G是哈密顿图。这里证明更深刻的结果:若3连通n≥3阶K1,3-free图G的满足1≤|N(x)∩(N(y)|≤α-1的不相邻的任两点x、y均有|N(x)∪(N(y)|≥(2n-6)/3,则G是哈密顿图。In 1998 a conjecture was suggested for the conference of Graph theory, combinatorics, and applications at Kalamazooin USA as follows： let G be a 3-connected K1.3-free graph of order n, if ｜N（x） ∪N（y） ｜≥（2n-6）/3 for each pair of nonadjacent vertices x,y, then G is Hamihonian. In this note we obtain the further result., let G be a 3- connected K1.3-free grah of order n, if ｜N（x） ∪ N（y） ｜（2n-6）/3 for each pair of nonadjacent vertices x,y with 1≤ I N（x） ∩ N（y） ｜≤a- 1, then G is Hamiltonian.

关 键 词：K1 3-free图 邻域并 广义邻域并 哈密顿图 

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