连通图可迹的新充分条件

New sufficient condition for making connected graphs be traceable

为了研究连通图的圈性结构,可以考虑局部性质与整体结构之间的密切关系.通过限定邻域并和邻域交的条件,证明了定理:如果对满足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.