Counting Hamilton decompositions of oriented graphs

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

External organisations

  • ETH Zurich
  • MIT

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.

Details

Original languageEnglish
Pages (from-to)6908-6933
Number of pages26
JournalInternational Mathematics Research Notices
Volume2018
Issue number22
Early online date16 May 2017
Publication statusPublished - 1 Nov 2018

Keywords

  • Hamilton cycle, graph decompositions