Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-09T06:04:39.457Z Has data issue: false hasContentIssue false

Hamiltonicity in random directed graphs is born resilient

Published online by Cambridge University Press:  24 June 2020

Richard Montgomery*
Affiliation:
School of Mathematics, University of Birmingham, Edgbaston, Birmingham B15 2TT, UK
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let $\{D_M\}_{M\geq 0}$ be the n-vertex random directed graph process, where $D_0$ is the empty directed graph on n vertices, and subsequent directed graphs in the sequence are obtained by the addition of a new directed edge uniformly at random. For each $$\varepsilon> 0$$, we show that, almost surely, any directed graph $D_M$ with minimum in- and out-degree at least 1 is not only Hamiltonian (as shown by Frieze), but remains Hamiltonian when edges are removed, as long as at most $1/2-\varepsilon$ of both the in- and out-edges incident to each vertex are removed. We say such a directed graph is $(1/2-\varepsilon)$-resiliently Hamiltonian. Furthermore, for each $\varepsilon > 0$, we show that, almost surely, each directed graph $D_M$ in the sequence is not $(1/2+\varepsilon)$-resiliently Hamiltonian.

This improves a result of Ferber, Nenadov, Noever, Peter and Škorić who showed, for each $\varepsilon > 0$, that the binomial random directed graph $D(n,p)$ is almost surely $(1/2-\varepsilon)$-resiliently Hamiltonian if $p=\omega(\log^8n/n)$.

Information

Type
Paper
Copyright
© The Author(s), 2020. Published by Cambridge University Press