Creating cycles in Walker-Breaker games

Abstract

We consider biased (1:b) Walker-Breaker games: Walker and Breaker alternately claim edges of the complete graph Kn, 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.