Recognition: unknown
Dirac's theorem for random graphs
classification
🧮 math.CO
keywords
randomdegreediraceverygraphgraphshamiltonianleast
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.