Avoider-enforcer star games

MaRDI QIDQ5249233zbMATH OpenFDO

Authors A. Grzesik, Mirjana Mikalački, Zoltán Lóránt Nagy, Alon Naor, Balázs Patkós, Fiona Skerman

Publication date 30 April 2015

Full work available at URL https://arxiv.org/abs/1302.2555, https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2482/0.html

zbMATH Keywords

positional gamescomplete graphavoider-enforcer games

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Abstract: In this paper, we study $(1:b)$ Avoider-Enforcer games played on the edge set of the complete graph on $n$ vertices. For every constant $kgeq3$ we analyse the $k$-star game, where Avoider tries to avoid claiming $k$ edges incident to the same vertex. We analyse both versions of Avoider-Enforcer games -- the strict and the monotone -- and for each provide explicit winning strategies for both players. We determine the order of magnitude of the threshold biases $f_m^{mon}athcalF$, $f_m^{-}athcalF$ and $f_m^{+}athcalF$, where $mathcalF$ is the hypergraph of the game.

Recommendations

• Avoider-enforcer star games
• Avoider-Enforcer: the rules of the game
• Avoider-enforcer: the rules of the game
• Keeping avoider's graph almost acyclic
• The star avoidance game

Cited in

(12)

• Avoider-enforcer: the rules of the game
• Avoider-Enforcer games played on edge disjoint hypergraphs
• \(\boldsymbol{H}\)-Games Played on Vertex Sets of Random Graphs
• Avoider-forcer games on hypergraphs with small rank
• The star avoidance game
• scientific article; zbMATH DE number 7379291 (Why is no real title available?)
• On avoider-enforcer games
• Fast winning strategies in avoider-enforcer games
• Avoider-Enforcer: the rules of the game
• On the separation conjecture in avoider-enforcer games
• Keeping avoider's graph almost acyclic
• Avoider-Enforcer games

This page was built for publication: Avoider-enforcer star games

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