Edge-disjoint Hamilton cycles in graphs
Edge-disjoint Hamilton cycles in graphs
复制标题
DOI：
10.1016/j.jctb.2011.10.005
复制
发表时间：
2009-08
期刊：
影响因子：
--
通讯作者：
Demetres Christofides;D. Kühn;Deryk Osthus
中科院分区：
文献类型：
--
作者：
Demetres Christofides;D. Kühn;Deryk Osthus
本文对Nash-Williams在1970年提出的一个问题给出了一个近似的回答：证明了对任意α>0，任意n阶充分大的最小度至少为（1/2+α）n的图至少含有n/8个边不交的汉密尔顿圈.更一般地说，我们给出了一个渐近最佳可能的答案的数量的边不相交的汉密尔顿圈，图G具有最小度δ必须有。我们还证明了Nash-Williams的另一个长期猜想的一个近似版本：证明了对任意α>0，任意n个顶点上最小度至少为（1/2+α）n的（几乎）正则且足够大的图几乎可以分解为边不相交的汉密尔顿圈.
In this paper we give an approximate answer to a question of Nash-Williams from 1970: we show that for every α>0, every sufficiently large graph on n vertices with minimum degree at least (1/2+α)n contains at least n/8 edge-disjoint Hamilton cycles. More generally, we give an asymptotically best possible answer for the number of edge-disjoint Hamilton cycles that a graph G with minimum degree δ must have. We also prove an approximate version of another long-standing conjecture of Nash-Williams: we show that for every α>0, every (almost) regular and sufficiently large graph on n vertices with minimum degree at least (1/2+α)n can be almost decomposed into edge-disjoint Hamilton cycles.