Counting Hamilton decompositions of oriented graphs

2016/09/29 by Ferber, Asaf, Long, Eoin, Sudakov, Benny · 3 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1609.09550

Abstract

A Hamilton cycle in a directed graph G is a cycle that passes through every vertex of G. A Hamiltonian 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 by Kühn and Osthus, 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 Hamiltonian decomposition, provided n=n(c) is sufficiently large. In this paper we address the natural question of estimating the number of such decompositions of G and show that this number is n^(1-o(1))cn2. In addition, we also obtain a new and much simpler proof for the approximate version of Kelly's conjecture.

Cited by

• On the pancyclicity of 2-connected [5,3]-graphs
• Optimal stability results on color-biased Hamilton cycles
• Hamilton decompositions of regular tripartite tournaments

Related

• The number of Hamiltonian decompositions of regular graphs
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• A survey on Hamilton cycles in directed graphs
• Hamilton Cycles in Dense Regular Digraphs and Oriented Graphs
• The generalizations of Hamiltonian in oriented graphs