Creating cycles in walker-breaker games

DOI10.1016/J.DISC.2016.03.007zbMATH Open1336.05092arXiv1505.02678OpenAlexW2250043689MaRDI QIDQ284747FDOQ284747

Authors: Dennis Clemens, Tuan Anh Tran 

Publication date: 18 May 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: We consider biased $(1:b)$ Walker-Breaker games: Walker and Breaker alternately claim edges of the complete graph $K_n$, Walker taking one edge and Breaker claiming $b$ edges in each round, with the constraint that Walker needs to choose her edges according to a walk. As questioned in a paper by Espig, Frieze, Krivelevich and Pegden, we study how long a cycle Walker is able to create and for which biases $b$ Walker has a chance to create a cycle of given constant length.

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

Recommendations

• On the WalkerMaker-WalkerBreaker games
• Walker-breaker games
• PathWalker-Breaker games on complete bipartite graphs
• Winning fast in biased maker-breaker games
• Fast strategies in biased Maker-Breaker games

zbMATH Keywords

positional gamescycle gamethreshold biaswalker-breaker

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24) Combinatorial games (91A46)

Cites Work

• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Biased positional games on matroids
• Positional games
• Asymptotic random graph intuition for the biased connectivity game
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• Biased Positional Games
• Combinatorial Games
• Biased positional games for which random strategies are nearly optimal
• On two problems regarding the Hamiltonian cycle game
• Weak and strong \(k\)-connectivity games
• Fast winning strategies in maker-breaker games
• On the threshold for the maker-breaker \(H\)-game
• Hitting time results for maker-breaker games
• Walker-Breaker Games
• Fast strategies in maker-breaker games played on random boards
• Dirac's theorem for random graphs
• Generating random graphs in biased maker-breaker games
• A sharp threshold for the Hamilton cycle Maker–Breaker game
• Positional games on random graphs
• Biased games on random boards

Cited In (9)

• On the WalkerMaker-WalkerBreaker games
• On the odd cycle game and connected rules
• Maker-Breaker total domination game on cubic graphs
• PathWalker-Breaker games on complete bipartite graphs
• Doubly biased walker-breaker games
• Connector-breaker games on random boards
• Walker-breaker games on \(G_{n, p}\)
• Odd and even cycles in maker-breaker games
• Spanning Structures in Walker–Breaker Games

This page was built for publication: Creating cycles in walker-breaker games

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