Random Matchings Which Induce Hamilton Cycles and Hamiltonian Decompositions of Random Regular Graphs

Jeong Han Kim, Nicholas C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

45 Citations (Scopus)

Abstract

Select four perfect matchings of 2n vertices, independently at random. We find the asymptotic probability that each of the first and second matchings forms a Hamilton cycle with each of the third and fourth. This is generalised to embrace any fixed number of perfect matchings, where a prescribed set of pairs of matchings must each produce Hamilton cycles (with suitable restrictions on the prescribed set of pairs). We also show how the result with four matchings implies that a random d-regular graph for fixed even d ≥ 4 asymptotically almost surely decomposes into d/2 Hamilton cycles. This completes a general result on the edge-decomposition of a random regular graph into regular spanning subgraphs of given degrees together with Hamilton cycles and verifies conjectures of Janson and of Robinson and Wormald.

Original languageEnglish
Pages (from-to)20-44
Number of pages25
JournalJournal of Combinatorial Theory, Series B
Volume81
Issue number1
DOIs
Publication statusPublished - 2001
Externally publishedYes

Cite this