一个Hamilton图的邻域交条件

A Neighborhood Intersection Condition for Hamiltonian Graphs

设Ｇ是２－连通图．如果对其任一３－独立集｛ｘ１，ｘ２，ｘ３｝，有ｘｉ（１≤ｉ≤３）使得Ｎ（ｘｉ）与∪ｊ≠ｉＮ（ｘｊ）至少有α（Ｇ）个公共元素，则Ｈａｍｉｌｔｏｎ图．这里，α（Ｇ）是Ｇ的独立数．

Let G be a 2-connected graph with independence number α(G) . If for every independent set {x 1,x 2,x 3} , there exists a vertex x i(1≤i≤3) such that N(x i) has at least α(G) common vertices with ∪j≠iN(x j) , then G is Hamiltonian.