20.500.12556/DiRROS-18631 Maker-Breaker domination game on trees when Staller wins 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. domination game Maker-Breaker game Maker-Breaker domination game hypergraphs trees subdivided stars caterpillars dominacijska igra igra izdelovalec-lomilec dominacijska igra izdelovalec-lomilec hipergrafi drevesa subdividirane zvezde gosenice true false true Angleški jezik Slovenski jezik Neznano 2024-04-08 11:24:34 2024-04-08 11:24:35 2024-04-09 03:40:10 0000-00-00 00:00:00 2023 0 0 21 str. no. 2, [article no.] 12 Vol. 25 2023 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2023-01-01 519.17 1365-8050 10.46298/dmtcs.10515 164065283 2212.06530.pdf 2212.06530.pdf 1 D9ABDC296CA33CAD76EB9FE4F838BFE7 6d4a3245b6cc2b82e5f91a71a061f8efc58641707b1f3a6af0be7d114ee3ade7 a8d3ade5-f579-11ee-ae20-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=25434 https://dmtcs.episciences.org/12202 1 0def177a-f579-11ee-ae20-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=25433 Inštitut za matematiko, fiziko in mehaniko 0 0 0