Doubly biased Walker-Breaker games

Abstract

© 2019, Univerzita Komenskeho. All rights reserved. We study doubly biased Walker-Breaker games, played on the edge set of a complete graph on n vertices, Kn. Walker-Breaker game is a variant of Maker- Breaker game, where Walker, playing the role of Maker, must choose her edges according to a walk, while Breaker has no restrictions on choosing his edges. Here we show that for b ≤ (image found), playing a (2: B) game on E(Kn), Walker can create a graph containing a spanning tree. Also, we determine a constant c > 0 such that Walker has a strategy to make a Hamilton cycle of Kn in the (2: Cn/ln n) game.