Hamiltonian decompositions of random bipartite regular graphs

Catherine Greenhill, Jeong Han Kim, Nicholas C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

5 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)195-222
Number of pages28
JournalJournal of Combinatorial Theory, Series B
Issue number2
Publication statusPublished - 2004
Externally publishedYes

Cite this