Random directed graphs are robustly Hamiltonian

Abstract

A classical theorem of Ghouila-Houri from 1960 asserts that every directed graph on $n$ vertices with minimum out-degree and in-degree at least $n/2$ contains a directed Hamilton cycle. In this paper we extend this theorem to a random directed graph $\mathcal{D}(n,p)$, that is, a directed graph in which every ordered pair $(u,v)$ becomes an arc with probability $p$ independently of all other pairs. Motivated by the study of resilience of properties of random graphs, we prove that if $p\gg \log n/\sqrt{n}$, then a.a.s. every subdigraph of $\mathcal{D}(n,p)$ with minimum out-degree and in-degree at least $(1/2+o(1))np$ contains a directed Hamilton cycle. The constant $1/2$ is asymptotically best possible. Our result also strengthens classical results about the existence of directed Hamilton cycles in random directed graphs.

35 pages, 1 figure

Cited by in corpus (1)

• Robust hamiltonicity of random directed graphs