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
SN - 1042-9832
VL - 10
SP - 305
EP - 321
JO - Random Structures and Algorithms
JF - Random Structures and Algorithms
IS - 3
ER -