Csilla Bujtás ; Pakanun Dokyeesun ; Sandi Klavžar - Maker-Breaker domination game on trees when Staller wins

dmtcs:10515 - Discrete Mathematics & Theoretical Computer Science, September 6, 2023, vol. 25:2 - https://doi.org/10.46298/dmtcs.10515
Maker-Breaker domination game on trees when Staller winsArticle

Authors: Csilla Bujtás ; Pakanun Dokyeesun ; Sandi Klavžar

    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.


    Volume: vol. 25:2
    Section: Graph Theory
    Published on: September 6, 2023
    Accepted on: July 13, 2023
    Submitted on: December 20, 2022
    Keywords: Mathematics - Combinatorics
    Funding:
      Source : OpenAIRE Graph
    • Pristine - Production process enhancement for photocatalytic treatment system for water; Code: 103536

    Consultation statistics

    This page has been seen 559 times.
    This article's PDF has been downloaded 383 times.