|
|
计算机科学 2007
A K1,3-free Hamiltonian Graphs
|
Abstract:
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是哈密顿图.
