Cores of random graphs are born Hamiltonian

Abstract

Let $(G_t{)}_{t\ge 0}$ 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 ${\tau }_k$ 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\ge 3$ the $k$-core is known to emerge via a discontinuous phase transition, where at time $t={\tau }_k$ its size jumps from 0 to linear in the number of vertices with high probability. It is believed that for any $k\ge 3$ the core is Hamiltonian upon creation w.h.p., and Bollobás, Cooper, Fenner and Frieze further conjectured that it in fact admits $\lfloor (k-1)/2\rfloor$ edge-disjoint 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\ge 15$ the $k$-core of $G_t$ is w.h.p. Hamiltonian for all $t\ge {\tau }_k$, i.e., immediately as the $k$-core appears and indefinitely afterwards. Moreover, we prove that for large enough fixed $k$ the $k$-core contains $\lfloor (k-3)/2\rfloor$ edge-disjoint Hamilton cycles w.h.p. for all $t\ge {\tau }_k$.

29 pages

References in corpus (3)

• The k-core and branching processes
• Asymptotic normality of the $k$-core in random graphs
• A simple solution to the k-core problem

Cited by in corpus (4)

• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Hamilton Cycles in Random Graphs: a bibliography
• A condition for Hamiltonicity in Sparse Random Graphs with a Fixed Degree Sequence
• Packing Hamilton Cycles in Cores of Random Graphs