### Abstract

Let (G_{t}) be the random graph process (G_{0}) is edgeless and G_{t} is obtained by adding a uniformly distributed new edge to G_{t}-1), and let tk denote the minimum time t such that the k-core of G_{t} (its unique maximal subgraph with minimum degree at least k) is nonempty. For any fixed k ≥3, the k-core is known to emerge via a discontinuous phase transition, where at time t = tk its size jumps from 0 to linear in the number of vertices with high probability (w.h.p.). It is believed that for any k ≥3, the core is Hamiltonian upon creation w.h.p., and Bollob́as, Cooper, Fenner and Frieze further conjectured that it in fact admits ≥(k - 1)/2 edgedisjoint Hamilton cycles. However, even the asymptotic threshold for Hamiltonicity of the k-core in G(n, p) was unknown for any k. We show here that for any fixed k ≥15, the k-core of G_{t} is w.h.p. Hamiltonian for all t ≥tk, that is, immediately as the k-core appears and indefinitely afterwards. Moreover, we prove that for large enough fixed k the k-core contains ≥(k - 3)/2 edge-disjoint Hamilton cycles w.h.p. for all t ≥tk.

Original language | English (US) |
---|---|

Pages (from-to) | 161-188 |

Number of pages | 28 |

Journal | Proceedings of the London Mathematical Society |

Volume | 109 |

Issue number | 1 |

DOIs | |

State | Published - Jul 2014 |

### ASJC Scopus subject areas

- Mathematics(all)

## Fingerprint Dive into the research topics of 'Cores of random graphs are born Hamiltonian'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the London Mathematical Society*,

*109*(1), 161-188. https://doi.org/10.1112/plms/pdu003