Hamilton decompositions of regular expanders: Applications
详细信息 查看全文
- 作者：Daniela K眉hn ; Deryk Osthus
- 关键词：Hamilton cycles ; Hamilton decompositions ; Tournaments ; Robust expansion
- 刊名：Journal of Combinatorial Theory, Series B
- 出版年：January, 2014
- 年：2014
- 卷：104
- 期：Complete
- 页码：1-27
- 全文大小：475 K
文摘
In a recent paper, we showed 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. The main consequence of this theorem is that every regular tournament on n vertices can be decomposed into edge-disjoint Hamilton cycles, whenever n is sufficiently large. This verified a conjecture of Kelly from 1968. In this paper, we derive a number of further consequences of our result on robust outexpanders, the main ones are the following:
- (i)
an undirected analogue of our result on robust outexpanders;
- (ii)
best possible bounds on the size of an optimal packing of edge-disjoint Hamilton cycles in a graph of minimum degree 未 for a large range of values for 未.
- (iii)
a similar result for digraphs of given minimum semidegree;
- (iv)
an approximate version of a conjecture of Nash-Williams on Hamilton decompositions of dense regular graphs;
- (v)
a verification of the 鈥榲ery dense鈥?case of a conjecture of Frieze and Krivelevich on packing edge-disjoint Hamilton cycles in random graphs;
- (vi)
a proof of a conjecture of Erd艖s on the size of an optimal packing of edge-disjoint Hamilton cycles in a random tournament.