Maker-Breaker total domination number

Articles in Press

Document Type : Special issue of CCO to honor Odile Favaron

Authors

1 Department of Mathematics, Mar Athanasius College, Kothamangalam, India

2 Department of Mathematics, Pavanatma College, Murickassery, India

3 Faculty of Mathematics and Physics, University of Ljubljana, Slovenia

4 Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

5 Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia

Abstract

The Maker-Breaker total domination number, $\gamma_{\rm MBT}(G)$, of a graph $G$ is introduced as the minimum number of moves of Dominator to win the Maker-Breaker total domination game, provided that he has a winning strategy and is the first to play. The Staller-start Maker-Breaker total domination number, $\gamma_{\rm MBT}'(G)$, is defined analogously for the game in which Staller starts. Upper and lower bounds on $\gamma_{\rm MBT}(G)$ and on $\gamma_{\rm MBT}'(G)$ are provided and demonstrated to be sharp. It is proved that for any pair of integers $(k,\ell)$ with $2\leq k\leq \ell$, (i) there exists a connected graph $G$ with $\gamma_{\rm MB}(G)=k$ and $\gamma_{\rm MBT}(G)=\ell$, (ii) there exists a connected graph $G'$ with $\gamma_{\rm MB}'(G')=k$ and $\gamma_{\rm MBT}'(G')=\ell$, and (iii) there there exists a connected graph $G''$ with $\gamma_{\rm MBT}(G'')=k$ and $\gamma_{\rm MBT}'(G'')=\ell$. Here, $\gamma_{\rm MB}$ and $\gamma_{\rm MB}'$ are corresponding invariants for the Maker-Breaker domination game.

Keywords

Main Subjects

References

[1] G. Bagan, E. Duchêne, V. Gledel, T. Lehtilä, and A. Parreau, Partition strategies for the Maker–Breaker domination game, Algorithmica 87 (2025), no. 2, 191–222. https://doi.org/10.1007/s00453-024-01280-x
[2] B. Brešar, M.A. Henning, S. Klavžar, and D.F. Rall, Domination Games Played on Graphs, Springer, 2021.
3] B. Brešar, S. Klavžar, and D.F. Rall, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010), no. 3, 979–991. https://doi.org/10.1137/100786800
[4] C. Bujtás and P. Dokyeesun, Fast winning strategies for Staller in the Maker–Breaker domination game, Discrete Appl. Math. 344 (2024), 10–22. https://doi.org/10.1016/j.dam.2023.11.015
[5] C. Bujtás, P. Dokyeesun, and S. Klavžar, Maker-Breaker domination game on trees when Staller wins, Discrete Math. Theo. Comput. Sci. 25 (2023), no. 2, https://doi.org/10.46298/dmtcs.10515
[6] A. Divakaran, T. Dravec, T. James, S. Klavžar, and L.S. Nair, Maker–Breaker domination game critical graphs, Discrete Appl. Math. 368 (2025), 126–134. https://doi.org/10.1016/j.dam.2025.02.038
[7] P. Dokyeesun, Maker-Breaker domination game on Cartesian products of graphs, Commun. Comb. Optim. (2025), In press. https://doi.org/10.22049/cco.2025.29866.2198
[8] E. Duchene, V. Gledel, A. Parreau, and G. Renault, Maker–Breaker domination game, Discrete Math. 343 (2020), no. 9, 111955. https://doi.org/10.1016/j.disc.2020.111955
[9] P. Erdös and J.L. Selfridge, On a combinatorial game, J. Combin. Theory Ser. A 14 (1973), no. 3, 298–301. https://doi.org/10.1016/0097-3165(73)90005-8
[10] O. Favaron, H. Karami, and S.M. Sheikholeslami, Game domination subdivision number of a graph, J. Comb. Optim. 30 (2015), no. 1, 109–119. https://doi.org/10.1007/s10878-013-9636-6
[11] J. Forcan and M. Mikalački, Maker-Breaker total domination game on cubic graphs, Discrete Math. Theo. Comput. Sci. 24 (2022), no. 1, 20. https://doi.org/10.46298/dmtcs.8529
[12] J. Forcan and J. Qi, Maker-Breaker domination number for cartesian products of path graphs $P_2$ and $P_n$, Discrete Math. Theo. Comput. Sci. 25 (2024), no. 2, 21. https://doi.org/10.46298/dmtcs.10465
[13] V. Gledel, M.A. Henning, V. Iršič, and S. Klavžar, Maker–Breaker total domination game, Discrete Appl. Math. 282 (2020), 96–107. https://doi.org/10.1016/j.dam.2019.11.004
[14] V. Gledel, V. Iršič, and S. Klavžar, Maker–Breaker domination number, Bull. Malays. Math. Sci. Soc. 42 (2019), no. 4, 1773–1789. https://doi.org/10.1007/s40840-019-00757-1
[15] A.W. Hales and R.I. Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), no. 2, 222–229.
[16] D. Hefetz, M. Krivelevich, M. Stojaković, and T. Szabó, Positional Games, vol. 44, Springer, 2014.
[17] M.A. Henning, S. Klavžar, and D.F. Rall, Total version of the domination game, Graphs Combin. 31 (2015), no. 5, 1453–1462. https://doi.org/10.1007/s00373-014-1470-9
[18] M.A. Henning, S. Klavžar, and D.F. Rall, The $\frac{4}{5}$ upper bound on the game total domination number, Combinatorica 37 (2017), no. 2, 223–251. https://doi.org/10.1007/s00493-015-3316-3
[19] V. Iršič, Effect of predomination and vertex removal on the game total domination number of a graph, Discrete Appl. Math. 257 (2019), 216–225. https://doi.org/10.1016/j.dam.2018.09.011
[20] Y. Jiang and M. Lu, Game total domination for cyclic bipartite graphs, Discrete Appl. Math. 265 (2019), 120–127.
https://doi.org/10.1016/j.dam.2019.03.009
[21] J. Portier and L.V. Versteegen, A proof of the $\frac{3}{4}$-conjecture for the total domination game, SIAM J. Discrete Math. 39 (2025), no. 1, 1–18. https://doi.org/10.1137/23M1551584
[22] M.L. Rahman and T. Watson, 6-uniform Maker-Breaker game is PSPACE-complete, Combinatorica 43 (2023), no. 3, 595–612. https://doi.org/10.1007/s00493-023-00026-7
[23] C. Worawannotai and K. Charoensitthichai, 4-total domination game critical graphs, Discrete Math. Algorithms Appl. 16 (2024), no. 5, 2350061. https://doi.org/10.1142/S1793830923500611
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 11 June 2026

Files

Share

How to cite

Statistics