Robust Hamiltonicity of Dirac graphs
By Michael Krivelevich, Choongbum Lee, Benny Sudakov. 2012
60 citations recorded by the source corpus.
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 ≥ 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.
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology
View Paper: https://www.semanticscholar.org/paper/ed7ee3f2558c132681bda47ff15ba6106b41a456
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Discrete Mathematics and Combinatorics
In Geometry and Topology
Citations in the corpus
- Hamilton cycles in graphs and hypergraphs: an extremal perspective (2014, methodology): “on this problem were obtained by Ben-Shimon, Krivelevich and Sudakov [12]. 4.3. Robust Hamiltonicity. An approach which can be viewed as ‘dual’ to resilience was taken by Krivelevich, Lee and Sudakov [79]. They proved the following extension of Dirac’s theorem, which one can view as a ‘robust’ versi”