Robust Hamiltonicity of Dirac graphs

DOI10.1090/S0002-9947-2014-05963-1MaRDI QIDQ5420107zbMATH OpenOpenAlexWikidataFDO

Authors Michael Krivelevich, Choongbum Lee, Benny Sudakov

Publication date 11 June 2014

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.2202

zbMATH Keywords

Dirac's theorem

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Games on graphs (graph-theoretic aspects) (05C57) Random graphs (graph-theoretic aspects) (05C80) Games involving graphs (91A43)

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 $pgeClogn/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/logn$ for some absolute constant $c>0$. Both of these results are tight up to a constant factor, and are proved under one general framework.

Recommendations

• Robust Hamiltonicity of random directed graphs
• Dirac type condition and Hamiltonian graphs
• Dirac type condition and Hamiltonian-connected graphs
• scientific article; zbMATH DE number 1187334
• Hamiltonian cycles in Dirac graphs
• Robust Hamiltonicity of random directed graphs: extended abstract
• Random directed graphs are robustly Hamiltonian
• On the number of Hamiltonian cycles in Dirac graphs
• Generalizations of Dirac's theorem in Hamiltonian graph theory -- a survey
• Hamiltonian cycles of certain kinds of graphs satisfying Dirac condition

Cites work

• Biased Positional Games
• Biased positional games and small hypergraphs with large covers
• Combinatorial Games
• Deterministic Graph Games and a Probabilistic Intuition
• Dirac's theorem for random graphs
• Distributing vertices along a Hamiltonian cycle in Dirac graphs
• Hamiltonian circuits in random graphs
• Hamiltonian cycles in Dirac graphs
• scientific article; zbMATH DE number 3815680 (Why is no real title available?)
• scientific article; zbMATH DE number 3970795 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 863469 (Why is no real title available?)
• scientific article; zbMATH DE number 5174567 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Increasing the chromatic number of a random graph
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Local resilience of almost spanning trees in random graphs
• Local resilience of graphs
• On a combinatorial game
• On the number of Hamiltonian cycles in Dirac graphs
• On the resilience of hamiltonicity and optimal packing of Hamilton cycles in random graphs
• On the resilience of long cycles in random graphs
• Proof of the Seymour conjecture for large graphs
• Remarks on positional games. I
• Resilient pancyclicity of random and pseudorandom graphs
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Threshold functions

Cited in

(37)

• Hamiltonicity below Dirac's condition
• Random directed graphs are robustly Hamiltonian
• Compatible Hamilton cycles in random graphs
• Dirac type condition and Hamiltonian-connected graphs
• Sharp thresholds for half-random games. I.
• On random k-out subgraphs of large graphs
• Dirac's theorem for random graphs
• Long paths and cycles in random subgraphs of graphs with large minimum degree
• Dirac's theorem for random regular graphs
• Maker-Breaker games on randomly perturbed graphs
• Crux and Long Cycles in Graphs
• Hitting time of edge disjoint Hamilton cycles in random subgraph processes on dense base graphs
• On Hamilton cycles in Erdős-Rényi subgraphs of large graphs
• A rainbow Dirac's theorem
• Graph Tilings in Incompatibility Systems
• Perfect matchings in random subgraphs of regular bipartite graphs
• Threshold for Steiner triple systems
• Counting oriented trees in digraphs with large minimum semidegree
• Chvátal-Erdős condition for pancyclicity
• Optimal spread for spanning subgraphs of Dirac hypergraphs
• Hamilton cycles in pseudorandom graphs
• A robust Corrádi-Hajnal theorem
• Compatible powers of Hamilton cycles in dense graphs
• Connectivity preserving Hamiltonian cycles in \(k\)-connected Dirac graphs
• Compatible Hamilton cycles in Dirac graphs
• The Hamilton space of pseudorandom graphs
• A generalization of Bondy's pancyclicity theorem
• Stability of transversal Hamilton cycles and paths
• Cyclic subsets in regular Dirac graphs
• Hamilton cycles in pseudorandom graphs (extended abstract)
• Chvátal-Erdős condition for pancyclicity (extended abstract)
• A generalization of Bondy's pancyclicity theorem (extended abstract)
• Hamiltonicity of random subgraphs of the hypercube
• Cyclic subsets of tournaments
• On the pancyclicity of 2-connected \([5, 3]\)-graphs
• Pancyclicity of Hamiltonian graphs
• Hamiltonian cycles in Dirac graphs

This page was built for publication: Robust Hamiltonicity of Dirac graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5420107)