Abstract
A Hamilton cycle in a graph Γ is a cycle passing through every vertex of Γ. A Hamiltonian decomposition of Γ is a partition of its edge set into disjoint Hamilton cycles. One of the oldest results in graph theory is Walecki’s theorem from the 19th century, showing that a complete graph K n on an odd number of vertices n has a Hamiltonian decomposition. This result was recently greatly extended by Kühn and Osthus. They proved that every r-regular n-vertex graph Γ with even degree r = cn for some fixed c > 1/2 has a Hamiltonian decomposition, provided n = n(c) is sufficiently large. In this paper we address the natural question of estimating H(Γ), the number of such decompositions of Γ. Our main result is that H(Γ) = r (1+o(1))nr/2. In particular, the number of Hamiltonian decompositions of K n is \({n^{\left( {1 + o\left( 1 \right)} \right){n^2}/2}}\).
Similar content being viewed by others
References
N. Alon, The maximum number of Hamiltonian paths in tournaments, Combinatorica 10 (1990), 319–324.
B. Alspach, The wonderful Walecki construction, Bulletin of the Institute of Combinatorics and its Applications 52 (2008), 7–20.
B. Alspach, J. C. Bermond and D. Sotteau, Decomposition into cycles I: Hamilton decompositions, in: Cycles and Rays (Montreal, PQ, 1987), NATO Advanced Science Institutes Series C: Mathematical and Physical Sciences, Vol. 301, Kluwer Academic Publishers, Dordrecht, 1990, pp. 9–18.
J. C. Bermond, O. Favaron and M. Maheo, Hamiltonian decomposition of Cayley graphs of degree 4, Journal of Combinatorial Theory. Series B 46 (1989), 142–153.
L. M. Brégman, Certain properties of nonnegative matrices and their permanents, Doklady Akademii Nauk SSSR 211 (1973), 27–30.
B. Csaba, A. Lo, D. Kühn, D. Osthus and A. Treglown, Proof of the 1-factorization and Hamilton decomposition conjectures, Memoirs of the American Mathematical Society 244 (2016).
B. Cuckler and J. Kahn, Hamilton cycles in Dirac graphs, Combinatorica 29 (2009), 299–326.
A. Ferber, M. Krivelevich and B. Sudakov, Counting and packing Hamilton cycles in dense graphs and oriented graphs, Journal of Combinatorial Theory. Series B 122 (2017), 196–220.
A. Fortuna, Z. Skupień and A. Żak, Maximizing hamiltonian pairs and k-sets via numerous leaves in a tree, Discrete Mathematics 309 (2009), 1788–1792.
A. Frieze, On the number of perfect matchings and Hamilton cycles in ϵ-regular nonbipartite graphs, Electronic Journal of Combinatorics 7 (2000), Research Paper 57.
A. Frieze and M. Krivelevich, On packing Hamilton cycles in ε-regular graphs, Journal of Combinatorial Theory. Series B 94 (2005), 159–172.
R. Glebov and M. Krivelevich, On the number of Hamilton cycles in sparse random graphs, SIAM Journal on Discrete Mathematics 27 (2013), 27–42.
S. Janson, The numbers of spanning trees, Hamilton cycles and perfect matchings in a random graph, Combinatorics, Probability and Computing 3 (1994), 97–126.
J. H. Kim and N. Wormald, Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs, Journal of Combinatorial Theory. Series B 81 (2001), 20–44.
F. Knox, D. Kühn and D. Osthus, Edge-disjoint Hamilton cycles in random graphs, Random Structures & Algorithms 46 (2015), 397–445.
M. Krivelevich, On the number of Hamilton cycles in pseudo-random graphs, Electronic Journal of Combinatorics 19 (2012), publication P25.
M. Krivelevich and B. Sudakov, Pseudo-random graphs, in More Sets, Graphs and Numbers, Bolyai Society Mathematical Studies, Vol. 15, Springer, Berlin, 2006, pp. 199–262.
D. Kühn and D. Osthus, Hamilton decompositions of regular expanders: a proof of Kelly’s conjecture for large tournaments, Advances in Mathematics 237 (2013), 62–146.
D. Kühn and D. Osthus, Hamilton decompositions of regular expanders: applications, Journal of Combinatorial Theory. Series B 104 (2014), 1–27.
L. Pósa, Hamiltonian circuits in random graphs, Discrete Mathematics 14 (1976), 359–364.
G. Ringel, Über drei kombinatorische Probleme am n-dimensionalen Würfel und Würfelgitter, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 20 (1955), 10–19.
B. Sudakov and V. Vu, Local resilience of graphs, Random Structures & Algorithms 33 (2008), 409–433.
Author information
Authors and Affiliations
Corresponding author
Additional information
Research supported by the ERC grant “High-dimensional combinatorics” at the Hebrew University of Jerusalem.
Research supported by Dr. Max Rössler, the Walter Haefner Foundation and the ETH Foundation.
Research supported in part by SNSF grant 200021-149111.
Rights and permissions
About this article
Cite this article
Glebov, R., Luria, Z. & Sudakov, B. The number of Hamiltonian decompositions of regular graphs. Isr. J. Math. 222, 91–108 (2017). https://doi.org/10.1007/s11856-017-1583-y
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11856-017-1583-y