Creating cycles in Walker-Breaker games

Publikationstyp
Journal Article
Date Issued
2016-04-27
Sprache
English
Author(s)
Clemens, Dennis  orcid-logo
Tran, Tuan  
Institut
Mathematik E-10  
TORE-URI
http://hdl.handle.net/11420/5484
Journal
Discrete mathematics  
Volume
339
Issue
8
Start Page
2113
End Page
2126
Citation
Discrete Mathematics 8 (339): 51-66 (2016)
Publisher DOI
10.1016/j.disc.2016.03.007
Scopus ID
2-s2.0-84964607693
Publisher
Elsevier
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.
Subjects
cycle game
positional games
threshold bias
Walker-Breaker
mathematics - combinatorics
DDC Class
510: Mathematik