| Naslov: | Fast winning strategies for Staller in the Maker-Breaker domination game |
|---|
| Avtorji: | ID Bujtás, Csilla (Avtor)
ID Dokyeesun, Pakanun (Avtor) |
|---|
| Datoteke: |  PDF - Predstavitvena datoteka, prenos (503,82 KB)
MD5: 632DBA700A188F73A5DD64B3BCC8F945
 URL - Izvorni URL, za dostop obiščite https://www.sciencedirect.com/science/article/pii/S0166218X23004286
|
|---|
| Jezik: | Angleški jezik |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: |  IMFM - Inštitut za matematiko, fiziko in mehaniko
|
|---|
| Povzetek: | 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. |
|---|
| Ključne besede: | domination game, Maker–Breaker game, winning number, Maker-Breaker domination game, closed neighborhood hypergraph |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 01.02.2024 |
|---|
| Leto izida: | 2024 |
|---|
| Št. strani: | str. 10-22 |
|---|
| Številčenje: | Vol. 344 |
|---|
| PID: | 20.500.12556/DiRROS-20509  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 0166-218X |
|---|
| DOI: | 10.1016/j.dam.2023.11.015 |
|---|
| COBISS.SI-ID: | 206680323 |
|---|
| Opomba: | Spletna objava: 9. 11. 2023;
|
|---|
| Datum objave v DiRROS: | 03.10.2024 |
|---|
| Število ogledov: | 208 |
|---|
| Število prenosov: | 103 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
