A sharp threshold for the Hamilton cycle Maker–Breaker game

DOI10.1002/RSA.20252MaRDI QIDQ3608315zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(21)

• Maker-breaker games on random geometric graphs
• 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
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• Complexity of maker-breaker games on edge sets of graphs
• 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

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)