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

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

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.

• Jezik: Angleški jezik
• Ključne besede: domination game, Maker–Breaker game, winning number, Maker-Breaker domination game, closed neighborhood hypergraph
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Datum objave: 01.02.2024
• Leto izida: 2024
• Št. strani: Str. 10-22
• Številčenje: Vol. 344
• PID: 20.500.12556/RUL-163171
• UDK: 519.17
• ISSN pri članku: 0166-218X
• DOI: 10.1016/j.dam.2023.11.015
• COBISS.SI-ID: 206680323
• Datum objave v RUL: 03.10.2024

Gradivo je del revije

• Naslov: Discrete applied mathematics
• Skrajšan naslov: Discrete appl. math.
• Založnik: Elsevier
• ISSN: 0166-218X
• COBISS.SI-ID: 25342464

Licence

• Licenca: CC BY-NC-ND 4.0, Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by-nc-nd/4.0/deed.sl
• Opis: Najbolj omejujoča licenca Creative Commons. Uporabniki lahko prenesejo in delijo delo v nekomercialne namene in ga ne smejo uporabiti za nobene druge namene.

Projekti

• Financer: ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
• Številka projekta: N1-0108
• Naslov: Prenos naboja v grafovski dominaciji

• Financer: ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
• Številka projekta: P1-0297
• Naslov: Teorija grafov