Resilience with respect to Hamiltonicity in random graphs

Main Article Content

Padraig Condon Alberto Espuny Díaz António Girão Jaehoon Kim Daniela Kühn Deryk Osthus

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.

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
Section
EUROCOMB 2019