Spanning Structures inWalker–Breaker Games
Учитавање...
Датум
2022
Аутори
Наслов журнала
Журнал ISSN
Наслов волумена
Издавач
Апстракт
We study the biased (2 : b) Walker–Breaker games, played on the edge set of the complete graph on n vertices, Kn. These games are a variant of the Maker–Breaker games with the restriction that Walker (playing the role of Maker) has to choose her edges according to a walk. We look at the two standard graph games – the Connectivity game and the Hamilton Cycle game and show that Walker can win both games even when playing against Breaker whose bias is of the order of magnitude n/ ln n.
Опис
Кључне речи
positional games, Walker–Breaker games, spanning structures