Discrete Mathematics & Theoretical Computer Science (Oct 2018)

Fast strategies in biased Maker--Breaker games

  • Mirjana Mikalački,
  • Miloš Stojaković

DOI
https://doi.org/10.23638/DMTCS-20-2-6
Journal volume & issue
Vol. vol. 20 no. 2, no. Graph Theory

Abstract

Read online

We study the biased $(1:b)$ Maker--Breaker positional games, played on the edge set of the complete graph on $n$ vertices, $K_n$. Given Breaker's bias $b$, possibly depending on $n$, we determine the bounds for the minimal number of moves, depending on $b$, in which Maker can win in each of the two standard graph games, the Perfect Matching game and the Hamilton Cycle game.

Keywords