TY - JOUR
T1 - Random Matchings Which Induce Hamilton Cycles and Hamiltonian Decompositions of Random Regular Graphs
AU - Kim, Jeong Han
AU - Wormald, Nicholas C.
PY - 2001
Y1 - 2001
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0012877456&partnerID=8YFLogxK
U2 - 10.1006/jctb.2000.1991
DO - 10.1006/jctb.2000.1991
M3 - Article
AN - SCOPUS:0012877456
SN - 0095-8956
VL - 81
SP - 20
EP - 44
JO - Journal of Combinatorial Theory, Series B
JF - Journal of Combinatorial Theory, Series B
IS - 1
ER -