独立集的度和与图的哈密尔顿性

Degree Sum of Independent Sets and Hamiltonicity of Graphs

关于哈密尔顿连通图的一个基本结果是Ore给出的：设G是n阶图,若对于任意两个不相邻顶点u和v,有d(u)+d(v)≥n+1,则G是哈密尔顿连通的．设G是一个图,对于任意u (?)V(G),令N(U)=∪_(u∈∪)N(u),d(U)=|N(U)|,称d(U)是U的度．本文利用独立集的度和得到如下结果：设s和t是正整数,G是(2s+2t+1)-连通n阶图．若对于任两个强不交独立集S,T,|S|=s,|T|=t,有d(S)+d(T)≥n+1．则G是哈密尔顿连通的．同时也得到图的哈密尔顿性的其它相关结果．两个独立集S和T称为强不交的,如果S∪T也是独立集．

One of the fundamental results concerning hamiltonian-connected graphs is due to Ore： If G is a graph of order n≥ 3 such that d（u） ＋d（v）≥ n＋ 1 for every pair of nonadjacent vertices u, v ∈ V（G）, then G is hamiltonian-connected. Let G be a graph, for any U C↓_ V（G）, let N（U） = Uu∈uN（u）, d（U） -= ｜N（U）｜. In this paper, we give the following result： Let s and t be two positive integers and G be a （2s ＋ 2t ＋ 1）-connected graph of order n. If d（S） ＋ d（T） ≥ n ＋ 1 for every two strongly disjoint independent sets S and T with ｜S｜ = s and ｜T｜ =- t, then G is hamiltonian-connected. Other related results are obtained too.