Maker-Breaker domination game on trees when Staller wins

Bujtás, Csilla (avtor), Dokyeesun, Pakanun (avtor), Klavžar, Sandi (avtor)

In the Maker-Breaker domination game played on a graph $G$, Dominator's goal is to select a dominating set and Staller's goal is to claim a closed neighborhood of some vertex. We study the cases when Staller can win the game. If Dominator (resp., Staller) starts the game, then $\gamma_{\rm SMB}(G)$ (resp., $\gamma_{\rm SMB}'(G)$) denotes the minimum number of moves Staller needs to win. For every positive integer $k$, trees $T$ with $\gamma_{\rm SMB}'(T)=k$ are characterized and a general upper bound on $\gamma_{\rm SMB}'$ is proved. Let $S = S(n_1,\dots, n_\ell)$ be the subdivided star obtained from the star with $\ell$ edges by subdividing its edges $n_1-1, \ldots, n_\ell-1$ times, respectively. Then $\gamma_{\rm SMB}'(S)$ is determined in all the cases except when $\ell\ge 4$ and each $n_i$ is even. The simplest formula is obtained when there are at least two odd $n_i$s. If ▫$n_1$▫ and $n_2$ are the two smallest such numbers, then $\gamma_{\rm SMB}'(S(n_1,\dots, n_\ell))=\lceil \log_2(n_1+n_2+1)\rceil$▫. For caterpillars, exact formulas for $\gamma_{\rm SMB}$ and for $\gamma_{\rm SMB}'$ are established.

• Jezik: Angleški jezik
• Ključne besede: domination game, Maker-Breaker game, Maker-Breaker domination game, hypergraphs, trees, subdivided stars, caterpillars
• 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.01.2023
• Leto izida: 2023
• Št. strani: 21 str.
• Številčenje: Vol. 25, no. 2, [article no.] 12
• PID: 20.500.12556/RUL-155607
• UDK: 519.17
• ISSN pri članku: 1365-8050
• DOI: 10.46298/dmtcs.10515
• COBISS.SI-ID: 164065283
• Datum objave v RUL: 08.04.2024

Gradivo je del revije

• Naslov: Discrete mathematics & theoretical computer science
• Skrajšan naslov: Discret. math. theor. comput. sci.
• Založnik: DMTCS
• ISSN: 1365-8050
• COBISS.SI-ID: 8089433

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: dominacijska igra, igra izdelovalec-lomilec, dominacijska igra izdelovalec-lomilec, hipergrafi, drevesa, subdividirane zvezde, gosenice