摘要
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.
出处
《计算机科学》
CSCD
北大核心
2007年第8期227-228,247,共3页
Computer Science
基金
海南省自然科学基金资助项目(批准号10501)
关键词
K1
3-free图
邻域并
广义邻域并
哈密顿图
K1,3-free graphs, Neighborhood unions, Generalizing neighborhood unions,Hamiltonian