Fast winning strategies in avoider-enforcer games

DOI10.1007/S00373-009-0870-8MaRDI QIDQ844236zbMATHOpenAlexFDO

Authors Dan Hefetz, Michael Krivelevich, Miloš Stojaković, Tibor Szabó

Publication date 18 January 2010

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0806.0280

Hypergraphs (05C65) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24) Combinatorial games (91A46)

Abstract: In numerous positional games the identity of the winner is easily determined. In this case one of the more interesting questions is not {em who} wins but rather {em how fast} can one win. These type of problems were studied earlier for Maker-Breaker games; here we initiate their study for unbiased Avoider-Enforcer games played on the edge set of the complete graph

K_{n}

on

n

vertices. For several games that are known to be an Enforcer's win, we estimate quite precisely the minimum number of moves Enforcer has to play in order to win. We consider the non-planarity game, the connectivity game and the non-bipartite game.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Fast winning strategies in avoider-enforcer games

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