Dirac's theorem for random graphs

Abstract

A classical theorem of Dirac from 1952 asserts that every graph on $n$ vertices with minimum degree at least $\lceil n/2\rceil$ is Hamiltonian. In this paper we extend this result to random graphs. Motivated by the study of resilience of random graph properties we prove that if $p\gg \log n/n$, then a.a.s. every subgraph of $G(n,p)$ with minimum degree at least $(1/2+o(1))np$ is Hamiltonian. Our result improves on previously known bounds, and answers an open problem of Sudakov and Vu. Both, the range of edge probability $p$ and the value of the constant 1/2 are asymptotically best possible.

14 pages,1 figures

References in corpus (1)

• Combinatorial theorems in sparse random sets

Cited by in corpus (2)

• Corrádi and Hajnal's theorem for sparse random graphs
• Robust Hamiltonicity of Dirac graphs