Jovana Forcan ; Mirjana Mikalački - Spanning Structures in Walker--Breaker Games

fi:9064 - Fundamenta Informaticae, March 10, 2022, Volume 185, Issue 1
Spanning Structures in Walker--Breaker Games

Authors: Jovana Forcan ; Mirjana Mikalački

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/ \ln n$.

Volume: Volume 185, Issue 1
Published on: March 10, 2022
Accepted on: February 10, 2022
Submitted on: February 8, 2022
Keywords: Mathematics - Combinatorics


Consultation statistics

This page has been seen 97 times.
This article's PDF has been downloaded 54 times.