Premium
Dirac's theorem for random graphs
Author(s) -
Lee Choongbum,
Sudakov Benny
Publication year - 2012
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20419
Subject(s) - random graph , combinatorics , mathematics , hamiltonian (control theory) , graph , hamiltonian path , discrete mathematics , mathematical optimization
A classical theorem of Dirac from 1952 asserts that every graph on n vertices with minimum degree at least \documentclass{article} \usepackage{mathrsfs} \usepackage{amsmath} \pagestyle{empty} \begin{document} \begin{align*}\left\lceil n/2 \right\rceil\end{align*} \end{document} 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 ≫ log n / n , then a.a.s. every subgraph of G ( n , p ) with minimum degree at least (1/2 + o (1)) n p 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. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012