TY - JOUR

T1 - 1-factorizations of random regular graphs

AU - Molloy, M. S.O.

AU - Robalewska, H.

AU - Robinson, R. W.

AU - Wormald, N. C.

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0031510220&partnerID=8YFLogxK

U2 - 10.1002/(SICI)1098-2418(199705)10:3<305::AID-RSA1>3.0.CO;2-#

DO - 10.1002/(SICI)1098-2418(199705)10:3<305::AID-RSA1>3.0.CO;2-#

M3 - Article

AN - SCOPUS:0031510220

VL - 10

SP - 305

EP - 321

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

IS - 3

ER -