# Resilience with respect to Hamiltonicity in random graphs

## Main Article Content

## Abstract

The local resilience of a graph $G$ with respect to a property $\mathcal{P}$ measures how much one has to change $G$ locally in order to destroy $\mathcal{P}$. We prove 'resilience' versions of several classical results about Hamiltonicity for the graph models $G_{n,p}$ and $G_{n,d}$.

In the setting of random regular graphs, we prove a resilience version of Dirac's theorem. More precisely, we show that, whenever $d$ is sufficiently large compared to $\varepsilon>0$, a.a.s. the following holds.Let $G'$ be any subgraph of the random $n$-vertex $d$-regular graph $G_{n,d}$ with minimum degree at least $(1/2+\varepsilon)d$.Then $G'$ is Hamiltonian.This proves a conjecture of Ben-Shimon, Krivelevich and Sudakov.

For the binomial random graph $G_{n,p}$, we prove a resilience version of Pósa's Hamiltonicity condition, and show that a natural guess for a resilience version of Chvátal's theorem fails to be true.

In the setting of random regular graphs, we prove a resilience version of Dirac's theorem. More precisely, we show that, whenever $d$ is sufficiently large compared to $\varepsilon>0$, a.a.s. the following holds.Let $G'$ be any subgraph of the random $n$-vertex $d$-regular graph $G_{n,d}$ with minimum degree at least $(1/2+\varepsilon)d$.Then $G'$ is Hamiltonian.This proves a conjecture of Ben-Shimon, Krivelevich and Sudakov.

For the binomial random graph $G_{n,p}$, we prove a resilience version of Pósa's Hamiltonicity condition, and show that a natural guess for a resilience version of Chvátal's theorem fails to be true.

## Article Details

How to Cite

Condon, P., Espuny Díaz, A., Girão, A., Kim, J., Kühn, D., & Osthus, D.
(2019).
Resilience with respect to Hamiltonicity in random graphs.

*Acta Mathematica Universitatis Comenianae, 88*(3), 547-551. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1193/692
Issue

Section

EUROCOMB 2019