摘要
1984年,Fan给出了著名的Fan定理:若2连通n阶图G的距离是2的任意两点x、y均有max{d(x),d(y)}≥n/2,则G是哈密尔顿图。本文证明深化Fan条件的结果:若2连通n阶图G的满足1≤|N(x)∩N(y)|≤α-1的任意两点x、y均有max{d(x),d(y)}≥n/2,则G是哈密尔顿图。而且本文给出的证明方法更简捷。
Let α to be independence number of graph G, in 1984 Fan showed: Let G be a 2-connected graph of order n, for every pair vertices x,y of d(x,y)=2, if max{d(x),d(y)}≥n/2, then G is Hamiltonian. In the paper we prove: Let G be a 2-connected graph of order n, for every pair of distinct nonadjacent vertices x and y with 1≤|N(x)∩N(y)|≤α-1, if max{d(x),d(y)}≥n/2, then G is Hamiltonian.
出处
《系统工程》
CSCD
北大核心
2004年第2期101-102,共2页
Systems Engineering
