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

A K_(1,3)-free Hamiltonian Graphs

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.