k-连通图中存在哈密尔顿圈的一个隐度条件

摘要

文中给出了强基本独立集的概念,并证明了如下定理:设G是一个具有n个顶点的k-连通图,其中k≥2.如果对任意一个具有k个顶点的强基本独立集S,都有max{d1(x)|x∈S}≥n/2,则G是哈密尔顿图.此定理推广了已有的几个有关图中哈密尔顿圈存在性的定理.