paper

Creating cycles in Walker-Breaker games

arXiv:1505.02678 · doi:10.1016/j.disc.2016.03.007

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.

23 pages, to appear in Discrete Mathematics