✦ LIBER ✦

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

✍ Scribed by Jeong Han Kim; Nicholas C. Wormald

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 215 KB
Volume: 81
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2000.1991

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Generating and Counting Hamilton Cycles

Generating and Counting Hamilton Cycles in Random Regular Graphs

✍ Alan Frieze; Mark Jerrum; Michael Molloy; Robert Robinson; Nicholas Wormald 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 216 KB

Let G be chosen uniformly at random from the set G G r, n of r-regular graphs w x Ž . with vertex set n . We describe polynomial time algorithms that whp i find a Ž . Hamilton cycle in G, and ii approximately count the number of Hamilton cycles in G.

Edge disjoint Hamilton cycles in sparse

Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at leastk

✍ Bollob�s, B.; Cooper, C.; Fenner, T. I.; Frieze, A. M. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 175 KB 👁 3 views

Let G n,m,k denote the space of simple graphs with n vertices, m edges, and minimum degree at least k, each graph G being equiprobable. Let G have property A k , if G contains (k -1)/2 edge disjoint Hamilton cycles, and, if k is even, a further edge disjoint matching of size n/2 . We prove that, for