Regular Factors Containing a Given Hamiltonian Cycle
Regular Factors Containing a Given Hamiltonian Cycle
复制标题
DOI：
10.1007/978-3-540-30540-8_14
复制
发表时间：
2003-09
影响因子：
1.8
通讯作者：
Haruhide Matsuda
中科院分区：
文献类型：
--
作者：
Haruhide Matsuda
设k≥1为整数，设G为具有足够大阶数的图。假设k为偶数，Gi的最小度数至少为k+2，Gi中每对不相邻顶点的度数和至少为n+α，其中奇数k的α=3，偶数k的α=4。 ThenG 有 ak- 因子（即 ak- 规则生成子图），它与给定的哈密顿循环边不相交。度数条件的下界是尖锐的。因此，我们有一个矿石类型条件，使图具有包含给定哈密顿循环的 ak- 因子。
Letk≥ 1 be an integer and letGbe a graph having a sufficiently large ordern. Suppose thatknis even, the minimum degree ofGis at leastk+ 2, and the degree sum of each pair of nonadjacent vertices inGis at leastn+α, whereα= 3 for oddkandα= 4 for evenk. ThenGhas ak– factor (i.e. ak– regular spanning subgraph) which is edge-disjoint from a given Hamiltonian cycle. The lower bound on the degree condition is sharp. As a consequence, we have an Ore-type condition for graphs to have ak– factor containing a given Hamiltonian cycle.