山东科学
山東科學
산동과학
SHANDONG SCIENCE
2011年
6期
8-11
,共4页
半无爪图%P3-支配图%Hamilton圈
半無爪圖%P3-支配圖%Hamilton圈
반무조도%P3-지배도%Hamilton권
quasi-claw-free graphs%P3-dominated graphs%Hamilton cycle
如果图G中任意一对距离为2的顶点x，y，有J（x，y）UJ’（x，y）≠φ，则称G为P3-支配图。本文证明了：设G是n（〉13）阶2-连通P3-支配图，如果对G中任意一对不相邻的顶点x，y，有2｜N（x）UN（y）｜＋d（x）＋d（y）≥2n-5，则G含有Hamilion圈或者G∈{K2,3,K1,1,3}。
如果圖G中任意一對距離為2的頂點x，y，有J（x，y）UJ’（x，y）≠φ，則稱G為P3-支配圖。本文證明瞭：設G是n（〉13）階2-連通P3-支配圖，如果對G中任意一對不相鄰的頂點x，y，有2｜N（x）UN（y）｜＋d（x）＋d（y）≥2n-5，則G含有Hamilion圈或者G∈{K2,3,K1,1,3}。
여과도G중임의일대거리위2적정점x，y，유J（x，y）UJ’（x，y）≠φ，칙칭G위P3-지배도。본문증명료：설G시n（〉13）계2-련통P3-지배도，여과대G중임의일대불상린적정점x，y，유2｜N（x）UN（y）｜＋d（x）＋d（y）≥2n-5，칙G함유Hamilion권혹자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}.
