Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Robust Hamiltonicity of Dirac graphs

Authors: Michael Krivelevich, Choongbum Lee and Benny Sudakov
Journal: Trans. Amer. Math. Soc. 366 (2014), 3095-3130
MSC (2010): Primary 05C38, 05C35, 05C57, 05C80
Published electronically: February 10, 2014
MathSciNet review: 3180741
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A graph is Hamiltonian if it contains a cycle which passes through every vertex of the graph exactly once. A classical theorem of Dirac from 1952 asserts that every graph on $ n$ vertices with minimum degree at least $ n/2$ is Hamiltonian. We refer to such graphs as Dirac graphs. In this paper we extend Dirac's theorem in two directions and show that Dirac graphs are robustly Hamiltonian in a very strong sense. First, we consider a random subgraph of a Dirac graph obtained by taking each edge independently with probability $ p$, and prove that there exists a constant $ C$ such that if $ p \ge C \log n / n$, then a.a.s. the resulting random subgraph is still Hamiltonian. Second, we prove that if a $ (1:b)$ Maker-Breaker game is played on a Dirac graph, then Maker can construct a Hamiltonian subgraph as long as the bias $ b$ is at most $ cn /\log n$ for some absolute constant $ c > 0$. Both of these results are tight up to a constant factor, and are proved under one general framework.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05C38, 05C35, 05C57, 05C80

Retrieve articles in all journals with MSC (2010): 05C38, 05C35, 05C57, 05C80

Additional Information

Michael Krivelevich
Affiliation: School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel

Choongbum Lee
Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Email: cb{\textunderscore}

Benny Sudakov
Affiliation: Department of Mathematics, ETH, 8092 Zurich, Switzerland – and – Department of Mathematics, University of California, Los Angeles, Los Angeles, California 90095

Received by editor(s): January 10, 2012
Received by editor(s) in revised form: September 21, 2012
Published electronically: February 10, 2014
Additional Notes: The first author’s research was supported in part by USA-Israel BSF Grant 2010115 and by grants 1063/08, 912/12 from the Israel Science Foundation
The second author’s research was supported in part by a Samsung Scholarship
The third author’s research was supported in part by SNSF grant 200021-149111 and by a USA-Israel BSF grant
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.