Packing Hamilton Cycles in Cores of Random Graphs

Abstract

Consider the random graph process $\{G_t{\}}_{t\ge 0}$. For $k\ge 3$ let $G_t^{(k)}$ denote the $k$-core of $G_t$ and let ${\tau }_k$ be the minimum $t$ such that the $k$-core of $G_t$ is nonempty. It is well known that w.h.p. for $G_{{\tau }_k}^{(k)}$ has linear size while it is believed to be Hamiltonian. Bollobás, Cooper, Fenner and Frieze further conjectured that w.h.p. $G_t^{(k)}$ spans $\lfloor \frac{k-1}{2}\rfloor$ edge-disjoint Hamilton cycles plus, when $k$ is even, a perfect matching for $t\ge {\tau }_k$. We prove that w.h.p.\@ if $k$ is odd then $G_t^{(k)}$ spans $\frac{k-3}{2}$ edge disjoint Hamilton cycles plus an additional 2-factor whereas if $k$ is even then it spans $\frac{k-2}{2}$ edge disjoint Hamilton cycles plus an additional matching of size $n/2-o(n)$ for $t\ge {\tau }_k$. In particular w.h.p. $G_t^{(k)}$ is Hamiltonian for $k\ge 4$ and $t\ge {\tau }_k$. This improves upon results of Krivelevich, Lubetzky and Sudakov.

References in corpus (1)

• Cores of random graphs are born Hamiltonian