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 GamesArticle

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 196 times.
    This article's PDF has been downloaded 147 times.