摘要
为了研究连通图的圈性结构,可以考虑局部性质与整体结构之间的密切关系.通过限定邻域并和邻域交的条件,证明了定理:如果对满足1≤N(x)∩N(y)≤α-1的任意不相邻的顶点x,y有N(x)∪N(y)≥n-δ-1,则G是可迹的(其中α表示连通图G的独立数);并根据结果给出连通图可迹的一个平凡的充分条件,此充分条件作为定理的推论说明定理在某种意义下是最好可能的.
In order to study the Hamihonian cycles of connected graphs, the relationship between the local property and the whole property might be considered. Based on the restriction of the conditions for the neighborhood union and neighborhood intersection, the following theorem was proven： if G is connected and the arbitrary pair of nonadjacent vertices （x, y）, such that1≤｜N（x）∩N（y）｜≤α-1
satisfies the condition｜N（x）∪N（y）｜≥n-δ-1then G is traceable （α stands for the independent sets of G）. A sufficient condition for the connected graphs was proposed according to the results. The sufficient condition, the inference of the theorem indicates that the above theorem, is the most possible in some sense.
出处
《河海大学学报（自然科学版）》
CAS
CSCD
北大核心
2009年第3期364-366,共3页
Journal of Hohai University(Natural Sciences)
基金
河海大学自然科学基金(2008428511)
关键词
连通图
HAMILTON
邻域并
邻域交
可迹
connected graph
Hamilton
neighborhood union
neighborhood intersection
traceability
