2-连通P_3-支配图的Hamilton圈

Hamilton cycle of 2-connected P_3-dominated graphs

如果图G中任意一对距离为2的顶点x,y,有J(x,y)∪J'(x,y)≠Ф,则称G为P3-支配图。本文证明了:设G是n(≥3)阶2-连通P3-支配图,如果对G中任意一对不相邻的顶点x,y,有2|N(x)∪N(y)|+d(x)+d(y)≥2n-5,则G含有Hamilton圈或者G∈{K2,3,K1,1,3}。

A graph G is a P3-dominated graph if J（x,y） UJ＇（x,y）≠φ for any pair of vertices x and y of d（x,y） =2. This paper proves that for any pair of non-adjacent vertices x and y in G,which is a 2.-connected P3-dominated graph of order n no less than 3, if 2｜N（x）UN（y）｜＋d（x）＋d（y）≥2n-5, then G has a Hamilton cycle or G∈{K2,3,K1,1,3}.