Abstract
A Hamilton cycle in a directed graph G is a cycle that passes through every vertex of G. A Hamilton decomposition of G is a partition of its edge set into disjoint Hamilton cycles. In the late 60s, Kelly conjectured that every regular tournament has a Hamilton decomposition. This conjecture was recently settled for large tournaments by Kühn and Osthus [13], who proved more generally that every r-regular n-vertex oriented graph G (without antiparallel edges) with r=cn for some fixed c>3/8 has a Hamilton decomposition, provided n=n(c) is sufficiently large. In this article, we address the natural question of estimating the number of such decompositions of G and show that this number is n(1−o(1))cn^2. In addition, we also obtain a new and much simpler proof for the approximate version of Kelly’s conjecture.
Original language | English |
---|---|
Pages (from-to) | 6908-6933 |
Number of pages | 26 |
Journal | International Mathematics Research Notices |
Volume | 2018 |
Issue number | 22 |
Early online date | 16 May 2017 |
DOIs | |
Publication status | Published - 1 Nov 2018 |
Keywords
- Hamilton cycle
- graph decompositions