Degree conditions for the existence of [k, k+1]-factors containing a given Hamiltonian cycle
Degree conditions for the existence of [k, k+1]-factors containing a given Hamiltonian cycle
复制标题
包含给定哈密顿循环的 [k, k 1]-因子存在的度条件
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Haruhide Matsuda
中科院分区：
文献类型：
--
作者：
Haruhide Matsuda
设k ≥ 2是一个整数，G是一个2-连通图|G| ≥ 3，最小度至少为k。假设|G| ≥ 8 k − 16（偶数）|G|和|G| ≥ 6 k − 13（奇数）|G|.证明了若max{degG（x），degG（y）} ≥| G| 1/2的任意一对不相邻顶点x和y。这是最好的可能性，因为在相同的条件下，存在一个没有k因子的图，它包含一个给定的哈密顿圈。的下界|G|也很锋利。
Let k ≥ 2 be an integer and G a 2-connected graph of order |G| ≥ 3 with minimum degree at least k. Suppose that |G| ≥ 8k − 16 for even |G| and |G| ≥ 6k − 13 for odd |G|. We prove that G has a [k, k + 1]-factor containing a given Hamiltonian cycle if max{degG(x), degG(y)} ≥ |G|/2 for each pair of nonadjacent vertices x and y in G. This is best possible in the sense that there exists a graph having no k-factor containing a given Hamiltonian cycle under the same conditions. The lower bound of |G| is also sharp.