Fast winning strategies for Staller in the Maker-Breaker domination game

Bujtás, Csilla (author), Dokyeesun, Pakanun (author)

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.

• Language: English
• Keywords: domination game, Maker–Breaker game, winning number, Maker-Breaker domination game, closed neighborhood hypergraph
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Publication date: 01.02.2024
• Year: 2024
• Number of pages: Str. 10-22
• Numbering: Vol. 344
• PID: 20.500.12556/RUL-163171
• UDC: 519.17
• ISSN on article: 0166-218X
• DOI: 10.1016/j.dam.2023.11.015
• COBISS.SI-ID: 206680323
• Publication date in RUL: 03.10.2024

Record is a part of a journal

• Title: Discrete applied mathematics
• Shortened title: Discrete appl. math.
• Publisher: Elsevier
• ISSN: 0166-218X
• COBISS.SI-ID: 25342464

Licences

• License: CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
• Link: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Description: The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.

Projects

• Funder: ARIS - Slovenian Research and Innovation Agency
• Project number: N1-0108
• Name: Prenos naboja v grafovski dominaciji

• Funder: ARIS - Slovenian Research and Innovation Agency
• Project number: P1-0297
• Name: Teorija grafov