Name
Abstract | ||
|---|---|---|
It is known that w.h.p. the hitting time tau(2 sigma) for the random graph process to have minimum degree 2s coincides with the hitting time for sigma edge-disjoint Hamilton cycles [4, 9, 13]. In this paper we prove an online version of this property. We show that, for a fixed integer sigma >= 2, if random edges of K-n are presented one by one then w.h.p. it is possible to colour the edges online with s colours so that at time tau(2 sigma) each colour class is Hamiltonian. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1017/S0963548318000159 | COMBINATORICS PROBABILITY & COMPUTING |
Field | DocType | Volume |
Integer,Discrete mathematics,Combinatorics,Disjoint sets,Random graph,Hamiltonian (quantum mechanics),Sigma,Hitting time,Mathematics | Journal | 27 |
Issue | ISSN | Citations |
SP4 | 0963-5483 | 1 |
PageRank | References | Authors |
0.39 | 5 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joseph Briggs | 1 | 1 | 0.39 |
| Alan M. Frieze | 2 | 4837 | 787.00 |
| michael krivelevich | 3 | 1688 | 179.90 |
| Po-Shen Loh | 4 | 133 | 18.68 |