Dirac's theorem for random graphs

Details Dirac's theorem for random graphs Dirac's theorem for random graphs

2011-08-11

arxiv.org/abs/1108.2502v3

Mathematics

Combinatorics

14 pages,1 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Dirac's theorem for random graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dirac's theorem for random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dirac's theorem for random graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-276799