A sharp threshold for the Hamilton cycle Maker–Breaker game

DOI10.1002/RSA.20252zbMATH Open1182.91050OpenAlexW4236302493MaRDI QIDQ3608315FDOQ3608315

Authors: Dan Hefetz, Michael Krivelevich, Miloš Stojaković, Tibor Szabó 

Publication date: 4 March 2009

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20252

Recommendations

• On two problems regarding the Hamiltonian cycle game
• On the threshold for the maker-breaker \(H\)-game
• Hamiltonian maker-breaker games on small graphs
• Positional games on random graphs
• Hamiltonian games

zbMATH Keywords

random graphcombinatorial gamesHamilton cycle

Mathematics Subject Classification ID

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

Cites Work

• On size Ramsey number of paths, trees, and circuits. I
• Combinatorial Games
• A Solution of the Shannon Switching Game
• Hamilton cycles in highly connected and expanding graphs

Cited In (21)

• Maker-Breaker games on randomly perturbed graphs
• Random directed graphs are robustly Hamiltonian
• Hamilton cycles in highly connected and expanding graphs
• Creating cycles in walker-breaker games
• Biased games on random boards
• A threshold for the maker-breaker clique game
• On two problems regarding the Hamiltonian cycle game
• Global maker-breaker games on sparse graphs
• Connector-breaker games on random boards
• Walker-breaker games on \(G_{n, p}\)
• Waiter-client and client-waiter Hamiltonicity games on random graphs
• Odd and even cycles in maker-breaker games
• Hamiltonian maker-breaker games on small graphs
• Complexity of maker-breaker games on edge sets of graphs
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• On the threshold for the maker-breaker \(H\)-game
• Hitting time results for maker-breaker games
• Local resilience and hamiltonicity maker-breaker games in random regular graphs
• The speed and threshold of the biased perfect matching and Hamilton cycle games
• On the Hamiltonicity of the \(k\)-regular graph game
• Maker-breaker games on random geometric graphs

This page was built for publication: A sharp threshold for the Hamilton cycle Maker–Breaker game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3608315)