Robust Hamiltonicity of Dirac graphs

DOI10.1090/S0002-9947-2014-05963-1zbMath1290.05098arXiv1201.2202OpenAlexW2052850567WikidataQ105584002 ScholiaQ105584002MaRDI QIDQ5420107

Choongbum Lee, Michael Krivelevich, Benjamin 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

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

Related Items (14)

Crux and Long Cycles in Graphs ⋮ Hitting Time of Edge Disjoint Hamilton Cycles in Random Subgraph Processes on Dense Base Graphs ⋮ Graph Tilings in Incompatibility Systems ⋮ Perfect matchings in random subgraphs of regular bipartite graphs ⋮ Sharp thresholds for half-random games I ⋮ Threshold for Steiner triple systems ⋮ On Hamilton cycles in Erdős‐Rényi subgraphs of large graphs ⋮ On randomk-out subgraphs of large graphs ⋮ A Rainbow Dirac's Theorem ⋮ Compatible Hamilton cycles in Dirac graphs ⋮ Random directed graphs are robustly Hamiltonian ⋮ Long paths and cycles in random subgraphs of graphs with large minimum degree ⋮ Compatible Hamilton cycles in random graphs ⋮ Maker-Breaker Games on Randomly Perturbed Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Increasing the chromatic number of a random graph
• Hamiltonian cycles in Dirac graphs
• Distributing vertices along a Hamiltonian cycle in Dirac graphs
• On the resilience of long cycles in random graphs
• Biased positional games and small hypergraphs with large covers
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Threshold functions
• Hamiltonian circuits in random graphs
• Proof of the Seymour conjecture for large graphs
• On the number of Hamiltonian cycles in Dirac graphs
• Local resilience of almost spanning trees in random graphs
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• Resilient Pancyclicity of Random and Pseudorandom Graphs
• Dirac's theorem for random graphs
• On the Resilience of Hamiltonicity and Optimal Packing of Hamilton Cycles in Random Graphs
• Local resilience of graphs
• Remarks on positional games. I
• Biased Positional Games
• Deterministic Graph Games and a Probabilistic Intuition
• Combinatorial Games
• On a combinatorial game

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