Hamilton decompositions of regular expanders: Applications

Research output: Contribution to journalArticlepeer-review

30 Citations (Scopus)
83 Downloads (Pure)

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 languageEnglish
Pages (from-to)1-27
Number of pages27
JournalJournal of Combinatorial Theory. Series B
Volume104
Issue number1
Early online date13 Nov 2013
DOIs
Publication statusPublished - 1 Jan 2014

Fingerprint

Dive into the research topics of 'Hamilton decompositions of regular expanders: Applications'. Together they form a unique fingerprint.

Cite this