Counting Hamilton decompositions of oriented graphs

DOI10.1093/IMRN/RNX085MaRDI QIDQ5233804zbMATH OpenOpenAlexFDO

Authors Asaf Ferber, Eoin Long, Benny Sudakov

Publication date 9 September 2019

Published in IMRN. International Mathematics Research Notices (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.09550, http://pure-oai.bham.ac.uk/ws/files/75178540/counting_ham_decomps_oriented.pdf

zbMATH Keywords

Hamilton cyclesHamilton decompositionrobust expanderstournamentstravelling salesman problem

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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 $60$s Kelly conjectured that every regular tournament has a Hamilton decomposition. This conjecture was recently settled by K"uhn 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))c{n}^2}$. In addition, we also obtain a new and much simpler proof for the approximate version of Kelly's conjecture.

Recommendations

• Hamilton decompositions of regular tournaments
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• A survey on Hamilton cycles in directed graphs
• The number of Hamiltonian decompositions of regular graphs
• Hamilton decompositions of regular expanders: applications

Cited in

(16)

• Hamiltonian numbers in oriented graphs
• The number of Hamiltonian decompositions of regular graphs
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Number of 1-factorizations of regular high-degree graphs
• Hamilton decompositions of regular tournaments
• A survey on Hamilton cycles in directed graphs
• An approximate version of Jackson's conjecture
• Path decompositions of tournaments
• Chvátal-Erdős condition for pancyclicity
• Hamilton cycles in pseudorandom graphs
• A generalization of Bondy's pancyclicity theorem
• Hamilton cycles in pseudorandom graphs (extended abstract)
• Chvátal-Erdős condition for pancyclicity (extended abstract)
• A generalization of Bondy's pancyclicity theorem (extended abstract)
• On the pancyclicity of 2-connected \([5, 3]\)-graphs
• Pancyclicity of Hamiltonian graphs

This page was built for publication: Counting Hamilton decompositions of oriented graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5233804)