20.500.12556/DiRROS-20509 Fast winning strategies for Staller in the Maker-Breaker domination game The Maker-Breaker domination game is played on a graph $G$ by two players, called Dominator and Staller, who alternately choose a vertex that has not been played so far. Dominator wins the game if his moves form a dominating set. Staller wins if she plays all vertices from a closed neighborhood of a vertex $v \in V(G)$. Dominator's fast winning strategies were studied earlier. In this work, we concentrate on the cases when Staller has a winning strategy in the game. We introduce the invariant $\gamma'_{\rm SMB}(G)$ (resp., $\gamma_{\rm SMB}(G)$) which is the smallest integer $k$ such that, under any strategy of Dominator, Staller can win the game by playing at most $k$ vertices, if Staller (resp., Dominator) plays first on the graph $G$. We prove some basic properties of $\gamma_{\rm SMB}(G)$ and $\gamma'_{\rm SMB}(G)$ and study the parameters' changes under some operators as taking the disjoint union of graphs or deleting a cut vertex. We show that the inequality $\delta(G)+1 \le \gamma'_{\rm SMB}(G) \le \gamma_{\rm SMB}(G)$ always holds and that for every three integers $r,s,t$ with $2\le r\le s\le t$, there exists a graph $G$ such that $\delta(G)+1 = r$, $\gamma'_{\rm SMB}(G) = s$, and $\gamma_{\rm SMB}(G) = t$. We prove exact formulas for $\gamma'_{\rm SMB}(G)$ where $G$ is a path, or it is a tadpole graph which is obtained from the disjoint union of a cycle and a path by adding one edge between them. domination game Maker–Breaker game winning number Maker-Breaker domination game closed neighborhood hypergraph true false true Angleški jezik Ni določen Neznano 2024-10-03 09:56:23 2024-10-03 09:56:23 2024-10-04 03:35:24 0000-00-00 00:00:00 2024 0 0 Spletna objava: 9. 11. 2023; str. 10-22 Vol. 344 Feb. 2024 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2024-02-01 519.17 0166-218X 10.1016/j.dam.2023.11.015 206680323 1-s2.0-S0166218X23004286-main-1.pdf 1-s2.0-S0166218X23004286-main-1.pdf 1 632DBA700A188F73A5DD64B3BCC8F945 7888330345663c5768528277b5bf16734de232b33cc822c76a6a28cb37d2be3a deb2b8b3-815d-11ef-a5bf-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=28908 https://www.sciencedirect.com/science/article/pii/S0166218X23004286 1 fcf948e8-815c-11ef-a5bf-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=28907 Inštitut za matematiko, fiziko in mehaniko 0 0 0