Spanning Structures in Walker--Breaker Games

DOI10.3233/FI-222104MaRDI QIDQ6322361arXivFDO

Authors Jovana Forcan, Mirjana Mikalački

Publication date 19 July 2019

Published in arXiv

Full work available at URL https://doi.org/10.3233/FI-222104

Mathematics Subject Classification ID

Combinatorial games (91A46)

arXiv classification

math.CO

Abstract: We study the biased $(2:b)$ Walker--Breaker games, played on the edge set of the complete graph on $n$ vertices, $K_n$. 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/lnn$.

This page was built for publication: Spanning Structures in Walker--Breaker Games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6322361)