TY - JOUR
T1 - Hamiltonian decompositions of random bipartite regular graphs
AU - Greenhill, Catherine
AU - Kim, Jeong Han
AU - Wormald, Nicholas C.
PY - 2004
Y1 - 2004
N2 - We prove a complete hamiltonian decomposition theorem for random bipartite regular graphs, thereby verifying a conjecture of Robinson and Wormald. The main step is to prove contiguity (a kind of asymptotic equivalence) of two probabilistic models of 4-regular bipartite graphs; namely, the uniform model, and the model obtained by taking the union of two independent, uniformly chosen bipartite Hamilton cycles, conditioned on forming no multiple edges. The proof uses the small subgraph conditioning method to establish contiguity, while the differential equation method is used to analyse a critical quantity.
AB - We prove a complete hamiltonian decomposition theorem for random bipartite regular graphs, thereby verifying a conjecture of Robinson and Wormald. The main step is to prove contiguity (a kind of asymptotic equivalence) of two probabilistic models of 4-regular bipartite graphs; namely, the uniform model, and the model obtained by taking the union of two independent, uniformly chosen bipartite Hamilton cycles, conditioned on forming no multiple edges. The proof uses the small subgraph conditioning method to establish contiguity, while the differential equation method is used to analyse a critical quantity.
UR - http://www.scopus.com/inward/record.url?scp=1442330970&partnerID=8YFLogxK
U2 - 10.1016/j.jctb.2003.07.001
DO - 10.1016/j.jctb.2003.07.001
M3 - Article
AN - SCOPUS:1442330970
VL - 90
SP - 195
EP - 222
JO - Journal of Combinatorial Theory, Series B
JF - Journal of Combinatorial Theory, Series B
SN - 0095-8956
IS - 2
ER -