Projects per year
Abstract
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 (n-1)/2 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 'very 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 Erdos on the size of an optimal packing of edge-disjoint Hamilton cycles in a random tournament. © 2013 Elsevier Inc.
Original language | English |
---|---|
Pages (from-to) | 1-27 |
Number of pages | 27 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 104 |
Issue number | 1 |
Early online date | 13 Nov 2013 |
DOIs | |
Publication status | Published - 1 Jan 2014 |
Fingerprint
Dive into the research topics of 'Hamilton decompositions of regular expanders: Applications'. Together they form a unique fingerprint.Projects
- 1 Finished
-
Edge-Colourings and Hamilton Decompostitions of Graphs
Engineering & Physical Science Research Council
1/06/12 → 30/09/14
Project: Research Councils