Robust Hamiltonicity of Dirac graphs

DOI10.1090/S0002-9947-2014-05963-1zbMATH Open1290.05098arXiv1201.2202OpenAlexW2052850567WikidataQ105584002 ScholiaQ105584002MaRDI QIDQ5420107FDOQ5420107

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)

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.

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

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

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)

Cites Work

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

Cited In (24)

• Long paths and cycles in random subgraphs of graphs with large minimum degree
• Random directed graphs are robustly Hamiltonian
• A Rainbow Dirac's Theorem
• Counting oriented trees in digraphs with large minimum semidegree
• Perfect matchings in random subgraphs of regular bipartite graphs
• Threshold for Steiner triple systems
• Chvátal-Erdős condition for pancyclicity
• Optimal spread for spanning subgraphs of Dirac hypergraphs
• Compatible Hamilton cycles in random graphs
• A robust Corrádi-Hajnal theorem
• Sharp thresholds for half-random games I
• Maker-Breaker Games on Randomly Perturbed Graphs
• Hamilton cycles in pseudorandom graphs
• Crux and Long Cycles in Graphs
• Hitting Time of Edge Disjoint Hamilton Cycles in Random Subgraph Processes on Dense Base Graphs
• Compatible powers of Hamilton cycles in dense graphs
• On Hamilton cycles in Erdős‐Rényi subgraphs of large graphs
• Hamiltonian cycles in Dirac graphs
• Connectivity preserving Hamiltonian cycles in \(k\)-connected Dirac graphs
• Dirac's theorem for random graphs
• On randomk-out subgraphs of large graphs
• Dirac type condition and Hamiltonian-connected graphs
• Graph Tilings in Incompatibility Systems
• Compatible Hamilton 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)