Creating cycles in walker-breaker games

DOI10.1016/J.DISC.2016.03.007MaRDI QIDQ284747zbMATH OpenOpenAlexFDO

Authors Dennis Clemens, Tuan Anh Tran

Publication date 18 May 2016

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

Cited in

(10)

• 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
• Connector-breaker games on random boards
• Doubly biased walker-breaker games
• Walker-breaker games
• 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)