Walker-breaker games

DOI10.1137/140953708zbMATH Open1320.05084arXiv1401.5538OpenAlexW2949871980WikidataQ57401415 ScholiaQ57401415MaRDI QIDQ2944455FDOQ2944455

Authors: Lisa Espig, Michael Krivelevich, Wesley Pegden, Alan Frieze 

Publication date: 2 September 2015

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

Abstract: We introduce and analyze the Walker-Breaker game, a variant of Maker-Breaker games where Maker is constrained to choose edges of a walk or path in a given graph G, with the goal of visiting as many vertices of the underlying graph as possible.

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

Recommendations

• On the WalkerMaker-WalkerBreaker games
• PathWalker-Breaker games on complete bipartite graphs
• Creating cycles in walker-breaker games
• Winning fast in fair biased maker-breaker games
• On the threshold for the maker-breaker \(H\)-game

zbMATH Keywords

random walkmaker-breaker gamesbox game

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Random walks on graphs (05C81) Games involving graphs (91A43) Combinatorial games (91A46)

Cites Work

• Maximum hitting time for random walks on graphs
• Biased Positional Games
• Combinatorial Games
• On a combinatorial game
• Fast winning strategies in maker-breaker games
• Optimal numberings and isoperimetric problems on graphs
• Balls and bins: A study in negative dependence
• A solution to the Box Game

Cited In (11)

• On the WalkerMaker-WalkerBreaker games
• Creating cycles in walker-breaker games
• On the odd cycle game and connected rules
• Maker-Breaker total domination game on cubic graphs
• On strong avoiding games
• 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}\)
• A strategy for isolator in the toucher-isolator game on trees
• Spanning Structures in Walker–Breaker Games

This page was built for publication: Walker-breaker games

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