Robust Hamiltonicity of Dirac graphs

DOI10.1090/S0002-9947-2014-05963-1zbMath1290.05098arXiv1201.2202WikidataQ105584002 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

05C35: Extremal problems in graph theory

05C80: Random graphs (graph-theoretic aspects)

91A43: Games involving graphs

05C38: Paths and cycles

05C45: Eulerian and Hamiltonian graphs

05C07: Vertex degrees

05C57: Games on graphs (graph-theoretic aspects)

Related Items

Long paths and cycles in random subgraphs of graphs with large minimum degree, 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, Compatible Hamilton cycles in Dirac graphs, Random directed graphs are robustly Hamiltonian, Compatible Hamilton cycles in random graphs, Sharp thresholds for half-random games I, On randomk-out subgraphs of large 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