Robust Hamiltonicity of Dirac graphs

DOI10.1090/S0002-9947-2014-05963-1MaRDI QIDQ5420107zbMATHOpenAlexWikidataFDO

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

Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Vertex degrees (05C07) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Games on graphs (graph-theoretic aspects) (05C57) 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

• 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?)
• 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
• 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

(25)

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

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)