Local Resilience and Hamiltonicity Maker–Breaker Games in Random Regular Graphs

DOI10.1017/S0963548310000453zbMath1232.91062arXiv0911.4351OpenAlexW2092565550MaRDI QIDQ3081327

Sonny Ben-Shimon, Michael Krivelevich, Benjamin Sudakov

Publication date: 7 March 2011

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Games involving graphs (91A43) Eulerian and Hamiltonian graphs (05C45)

Related Items

Corrádi and Hajnal's Theorem for Sparse Random Graphs, Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs, Fast winning strategies for the maker-breaker domination game, Dirac's theorem for random graphs, Long cycles in subgraphs of (pseudo)random directed graphs, On the Hamiltonicity of random bipartite graphs, Hitting time results for Maker-Breaker games, Pancyclic subgraphs of random graphs, Some remarks on rainbow connectivity, Generating random graphs in biased Maker-Breaker games, Robust Hamiltonicity of random directed graphs, Discrepancies of spanning trees and Hamilton cycles, Spanning Trees at the Connectivity Threshold, Fast winning strategies for staller in the maker-breaker domination game, Random directed graphs are robustly Hamiltonian, Bandwidth theorem for random graphs, Maker-breaker domination number, Dirac’s theorem for random regular graphs, Hamiltonicity in random graphs is born resilient, Maker‐breaker games on random geometric graphs

Cites Work

• Hamilton cycles in highly connected and expanding graphs
• Small subgraphs of random regular graphs
• On two Hamilton cycle problems in random graphs
• Almost all regular graphs are Hamiltonian
• Hamiltonian cycles in random regular graphs
• Finding Hamilton cycles in sparse random graphs
• The asymptotic connectivity of labelled regular graphs
• On the second eigenvalue of a graph
• Hamiltonian circuits in random graphs
• Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs
• Sandwiching random graphs: universality between random graph models
• Random regular graphs of high degree
• Resilient Pancyclicity of Random and Pseudorandom Graphs
• Permutation Pseudographs and Contiguity
• Local resilience of graphs
• A sharp threshold for the Hamilton cycle Maker–Breaker game
• Almost all cubic graphs are Hamiltonian
• Biased Positional Games
• Optimal Construction of Edge-Disjoint Paths in Random Graphs
• Almost all regular graphs are hamiltonian
• Sparse pseudo‐random graphs are Hamiltonian
• On the asymmetry of random regular graphs and random graphs
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• A Solution of the Shannon Switching Game