哈密顿图的邻域交和邻域并条件

Neighborhood Intersection and Neighborhood Union Conditions for Hamiltonian Graphs

记δ和α分别为图G=(V,E)的最小度和独立数,1991年Faudree等人和尹家洪分别得到:“若2连通n阶图G的不相邻的任意两点x、y均有｜N(x)∪N(y)｜≥n-δ,则G是哈密尔顿图”和“若2连通n阶图G的长为2的任意两点x、y均有｜N(x)∪N(y)｜≥n-δ,则G是哈密尔顿图”。这里得到结果:若2连通n阶图G的满足1≤｜N(x)∩N(y)｜≤α-1的不相邻的任两点x、y均有｜N(x)∪N(y)｜≥n-δ,则G是哈密尔顿图。此结果推广Faudree等人和尹家洪的结果。

Let G be a simple graph, δ and α be minimum degree and independent degree of G, respectively. In 1991 Faudree et al considered neighborhood union condition ｜N（x）∪N（y）｜≥n-δ for each pair of non-adjacent vertices x,y for Hamiltonian. Yin Jiahong considered further condition ｜N（x）∪N（y）｜≥n-δ for each pair of nonadjacent vertices x,y with d（x,y）=2 for Hamiltonian. The new sufficient condition of generalization of the above two conditions for a graph to be Hamihonian graph is considered and show that if G is a 2-connected graph of order n, if ｜N（x）∪N（y）｜≥n-δ for each pair of non-adjacent vertices x,y with 1 ｜N（x）∩N（y）｜≤α-1, then G is Hamiltonian.