独立集的邻域并和图的哈密尔顿性

The Neighborhood Union of Independent Sets and Hamiltonicity of Graphs

设G是一个图，对于两个正整数s和t，记σs.t=S,t{ ｜ N（S） ｜ ＋ ｜ N（T） ｜- 1/2 ｜N（S）∩N（T）｜： ｜ S｜ = s, ｜ T｜ = t,且S∪T是G的独立集}．本文利用插点方法，给出了关于（s＋t）或（s＋t＋1）一连通图g是哈密顿的，哈密尔顿连通的或1-哈密尔顿的统一的证明．其充分条件是关于σt,s与n（Y）的不等式，这里Y-S∪T是图G的任一独立集，n（Y）= ｜{v∈V（G）：dist（v,Y）≤2}｜．

Let G be a graph. For two positive integers s and t, set σs.t = min S,t{ ｜ N（S） ｜ ＋ ｜ N（T） ｜- 1/2 ｜N（S）∩N（T）｜： ｜ S｜ = s, ｜ T｜ = t, and S ∪ T is an independent set of Gt. In this paper, we will use the technique of the vertex insertion on l-connected （ 1 = s ＋ t or s ＋ t ＋ 1 ） graphs to provide a unified proof for G to be lmmilonian, hamilton-connected, or l-hamiltonian the sufficient conditioos are expressed by the inequality concerning σt,s, and n（Y）, where Y=S ∪ T, and n（Y）= ｜{v∈V（G）： dist（v,Y）≤2}｜.