Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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
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
Email: krivelev@post.tau.ac.il

Choongbum Lee
Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Email: cb{\textunderscore}lee@math.mit.edu

Benny Sudakov
Affiliation: Department of Mathematics, ETH, 8092 Zurich, Switzerland – and – Department of Mathematics, University of California, Los Angeles, Los Angeles, California 90095
Email: benjamin.sudakov@math.ethz.ch

DOI: http://dx.doi.org/10.1090/S0002-9947-2014-05963-1
PII: S 0002-9947(2014)05963-1
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.