Opuscula Mathematica
Opuscula Math. 41, no. 4 (2021), 453-464

Total connected domination game

Csilla Bujtás
Michael A. Henning
Vesna Iršič
Sandi Klavžar
Abstract. The (total) connected domination game on a graph \(G\) is played by two players, Dominator and Staller, according to the standard (total) domination game with the additional requirement that at each stage of the game the selected vertices induce a connected subgraph of \(G\). If Dominator starts the game and both players play optimally, then the number of vertices selected during the game is the (total) connected game domination number (\(\gamma_{\rm tcg}(G)\)) \(\gamma_{\rm cg}(G)\) of \(G\). We show that \(\gamma_{\rm tcg}(G) \in \{\gamma_{\rm cg}(G),\gamma_{\rm cg}(G) + 1,\gamma_{\rm cg}(G) + 2\}\), and consequently define \(G\) as Class \(i\) if \(\gamma_{\rm tcg}(G) = \gamma_{\rm cg} + i\) for \(i \in \{0,1,2\}\). A large family of Class \(0\) graphs is constructed which contains all connected Cartesian product graphs and connected direct product graphs with minumum degree at least \(2\). We show that no tree is Class \(2\) and characterize Class \(1\) trees. We provide an infinite family of Class \(2\) bipartite graphs.
Keywords: connected domination game, total connected domination game, graph product, tree.
Mathematics Subject Classification: 05C57, 05C69, 91A43.
Full text (pdf)
References ▼
  1. [1] M. Borowiecki, A. Fiedorowicz, E. Sidorowicz, Connected domination game, Appl. Anal. Discrete Math. 13 (2019), 261-289.
  2. [2] B. Brešar, M.A. Henning, The game total domination problem is log-complete in PSPACE, Inform. Process. Lett. 126 (2017), 12-17.
  3. [3] B. Brešar, S. Klavžar, D.F. Rall, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010), 979-991.
  4. [4] Cs. Bujtás, On the game domination number of graphs with given minimum degree, Electron. J. Combin. 22 (2015), #P3.29.
  5. [5] Cs. Bujtás, On the game total domination number, Graphs Combin. 34 (2018), 415-425.
  6. [6] Cs. Bujtás, P. Dokyeesun, V. Iršič, S. Klavžar, Connected domination game played on Cartesian products, Open Math. 17 (2019), 1269-1280.
  7. [7] M. Dettlaff, J. Raczek, I.G. Yero, Edge subdivision and edge multisubdivision versus some domination related parameters in generalized corona graphs, Opuscula Math. 36 (2016), 575-588.
  8. [8] P. Dorbec, M.A. Henning, Game total domination for cycles and paths, Discrete Appl. Math. 208 (2016), 7-18.
  9. [9] P. Dorbec, G. Košmrlj, G. Renault, The domination game played on unions of graphs, Discrete Math. 338 (2015), 71-79.
  10. [10] R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, 2nd ed., CRC Press, Boca Raton, FL, 2011.
  11. [11] M.A. Henning, S. Klavžar, D.F. Rall, Total version of the domination game, Graphs Combin. 31 (2015), 1453-1462.
  12. [12] M.A. Henning, S. Klavžar, D.F. Rall, The 4/5 upper bound on the game total domination number, Combinatorica 37 (2017), 223-251.
  13. [13] M.A. Henning, D.F. Rall, Progress towards the total domination game 3/4-conjecture, Discrete Math. 339 (2016), 2620-2627.
  14. [14] M.A. Henning, A. Yeo, Total Domination in Graphs, Springer Monographs in Mathematics, 2013.
  15. [15] 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.
  16. [16] V. Iršič, Connected domination game: predomination, Staller-start game, and lexicographic products, arXiv:1902.02087 [Math.CO] (6 Feb 2019).
  17. [17] T. James, S. Klavžar, A. Vijayakumar, The domination game on split graphs, Bull. Aust. Math. Soc. 99 (2019), 327-337.
  18. [18] W.B. Kinnersley, D.B. West, R. Zamani, Extremal problems for game domination number, SIAM J. Discrete Math. 27 (2013), 2090-2107.
  19. [19] S. Klavžar, D.F. Rall, Domination game and minimal edge cuts, Discrete Math. 341 (2019), 951-958.
  20. [20] K. Xu, X. Li, On domination game stable graphs and domination game edge-critical graphs, Discrete Appl. Math. 250 (2018), 47-56.
About the authors ▼
Csilla Bujtás (corresponding author)
https://orcid.org/0000-0002-0511-5291
University of Ljubljana, Faculty of Mathematics and Physics, Ljubljana, Slovenia
Michael A. Henning
University of Johannesburg, Department of Mathematics and Applied Mathematics, Auckland Park, 2006 South Africa
Vesna Iršič
University of Ljubljana, Faculty of Mathematics and Physics, Ljubljana, Slovenia; Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
Sandi Klavžar
University of Ljubljana, Faculty of Mathematics and Physics, Ljubljana, Slovenia; Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia; University of Maribor, Faculty of Natural Sciences and Mathematics, Maribor, Slovenia
About the article ▼
Communicated by Dalibor Fronček.
Received: 2020-10-09.
Revised: 2021-03-15.
Accepted: 2021-03-17.
Published online: 2021-07-09.
Cite this article as ▼
Csilla Bujtás, Michael A. Henning, Vesna Iršič, Sandi Klavžar, Total connected domination game, Opuscula Math. 41, no. 4 (2021), 453-464, https://doi.org/10.7494/OpMath.2021.41.4.453.
Download this article's citation as: