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

Neighborhood Intersection and Neighborhood Union Conditions for Hamiltonian Graphs

作　　者：陈德钦[1] 赵克文[1] 

机构地区：[1]琼州大学数学系,三亚572022

出　　处：《科学技术与工程》2006年第8期1045-1046,1051,共3页Science Technology and Engineering

基　　金：海南省自然科学基金(10501)资助

摘　　要：记δ和α分别为图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.

关 键 词：哈密尔顿图 邻域并条件 新的条件 

分 类 号：O157.5[理学—数学]