Hamiltonicity in random graphs is born resilient

with minimum degree at least 2 is not only Hamiltonian (as shown by Bollob'as), but remains Hamiltonian despite the removal of any set of edges, as long as at most

(1 / 2 - v a r e p s i l o n)

of the edges incident to each vertex are removed. We say that such a graph is

(1 / 2 - v a r e p s i l o n)

-resiliently Hamiltonian. Furthermore, for each

e p s i l o n > 0

, we show that, almost surely, each graph

G_{M}

is not

(1 / 2 + v a r e p s i l o n)

-resiliently Hamiltonian. These results strengthen those by Lee and Sudakov on the likely resilience of Hamiltonicity in the binomial random graph. For each

k

, we denote by

G^{(k)}

the (possibly empty) maximal subgraph with minimum degree at least

k

of a graph

G

. That is, the

k

-core of

G

. Krivelevich, Lubetzky and Sudakov have shown that, for each

k g e q 15

, in almost every random graph process

{G_{M}}_{M g e q 0}

, every non-empty

k

-core is Hamiltonian. We show that, for each

v a r e p s i l o n > 0

and

k g e q k_{0} (v a r e p s i l o n)

, in almost every random graph process

{G_{M}}_{M g e q 0}

, every non-empty

k

-core is

(1 / 2 - v a r e p s i l o n)

-resiliently Hamiltonian, but not

(1 / 2 + v a r e p s i l o n)

-resiliently Hamiltonian.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: Hamiltonicity in random graphs is born resilient

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2338643)