1-factorizations of random regular graphs

M. S.O. Molloy, H. Robalewska, R. W. Robinson, N. C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

29 Citations (Scopus)

Abstract

It is shown that for each r ≥ 3, a random r-regular graph on 2n vertices is equivalent in a certain sense to a set of r randomly chosen disjoint perfect matchings of the 2n vertices, as n → ∞. This equivalence of two sequences of probabilistic spaces, called contiguity, occurs when all events almost sure in one sequence of spaces are almost sure in the other, and vice versa. The corresponding statement is also shown for bipartite graphs, and from this it is shown that a random r-regular simple digraph is almost surely strongly r-connected for all r ≥ 2.

Original languageEnglish
Pages (from-to)305-321
Number of pages17
JournalRandom Structures & Algorithms
Volume10
Issue number3
DOIs
Publication statusPublished - 1997
Externally publishedYes

Cite this