Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
复制标题
常规扩展器的汉密尔顿分解：大型锦标赛凯利猜想的证明
DOI：
10.1016/j.aim.2013.01.005
复制
发表时间：
2013
影响因子：
1.7
通讯作者：
Kühn D
中科院分区：
文献类型：
--
作者：
Kühn D
Kelly的一个长期猜想指出，n个顶点上的每个规则锦标赛可以分解为(n−1)/2个边不相交的汉密尔顿环。我们证明了这个猜想的大n。事实上，我们证明了一个更一般的结果，基于我们最近的鲁棒展开的概念和分解图的新方法。我们证明了n个顶点上的每一个足够大的正则有向图G，它的度在n上是线性的，并且是一个鲁棒的外展开式，它被分解成边不相交的汉密尔顿环。这使我们能够获得许多进一步的结果，例如，作为一个特殊情况，我们证实了Erdős关于在随机锦标赛中包装汉密尔顿循环的猜想。作为主要结果的推论，我们也得到了在无向图中填充Hamilton环的几个结果，例如给出了关于Nash-Williams猜想的最著名的结果。我们还将我们的结果应用于求解Glover和Punnen以及Alon、Gutin和Krivelevich等人提出的非对称旅行商问题的支配比问题。
A long-standing conjecture of Kelly states that every regular tournament on n vertices can be decomposed into (n−1)/2 edge-disjoint Hamilton cycles. We prove this conjecture for large n. In fact, we prove a far more general result, based on our recent concept of robust expansion and a new method for decomposing graphs. We show that every sufficiently large regular digraph G on n vertices whose degree is linear in n and which is a robust outexpander has a decomposition into edge-disjoint Hamilton cycles. This enables us to obtain numerous further results, e.g. as a special case we confirm a conjecture of Erdős on packing Hamilton cycles in random tournaments. As corollaries to the main result, we also obtain several results on packing Hamilton cycles in undirected graphs, giving e.g. the best known result on a conjecture of Nash-Williams. We also apply our result to solve a problem on the domination ratio of the Asymmetric Travelling Salesman problem, which was raised e.g. by Glover and Punnen as well as Alon, Gutin and Krivelevich.