Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/j.jctb.2003.07.001 | J. Comb. Theory, Ser. B |
Keywords | DocType | Volume |
uniform model,differential equation method,asymptotic equivalence,probabilistic model,complete hamiltonian decomposition theorem,4-regular bipartite graph,bipartite hamilton cycle,small subgraph conditioning method,hamiltonian decomposition,critical quantity,random bipartite regular graph,bipartite graph,hamilton cycle,regular graph | Journal | 90 |
Issue | ISSN | Citations |
2 | Journal of Combinatorial Theory, Series B | 3 |
PageRank | References | Authors |
0.40 | 6 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Catherine Greenhill | 1 | 628 | 62.40 |
| Jeong Han Kim | 2 | 699 | 60.19 |
| Nicholas C. Wormald | 3 | 1506 | 230.43 |