Total connected domination game

• Autorzy: Bujtas Csilla , Henning Michael A. , Irsic Vesna , Klavzar Sandi

Identyfikatory

DOI

10.7494/OpMath.2021.41.4.453

• Języki publikacji: EN

Abstrakty

EN

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 [formulas] of G. We show that [formulas], and consequently define G as Class i if [formula] for i ∈ {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 minimum 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.

Słowa kluczowe

EN

connected domination game; total connected domination game; graph product; tree

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2021
• Tom: Vol. 41, no. 4
• Strony: 453--464
• Opis fizyczny: BIbliogr. 20 poz.

Twórcy

autor

Bujtas Csilla

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

• https://orcid.org/0000-0002-0511-5291

autor

Henning Michael A.

• University of Johannesburg Department of Mathematics and Applied Mathematics Auckland Park, 2006 South Africa

autor

Irsic Vesna

• University of Ljubljana Faculty of Mathematics and Physics Ljubljana, Slovenia
• Institute of Mathematics, Physics and Mechanics Ljubljana, Slovenia

autor

Klavzar Sandi

• 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

Bibliografia

• [1] M. Borowiecki, A. Fiedorowicz, E. Sidorowicz, Connected domination game, Appl. Anal. Discrete Math. 13 (2019), 261-289.
• [2] B. Bresar, M.A. Henning, The game total domination problem is log-complete in PSPACE, Inform. Process. Lett. 126 (2017), 12-17.
• [3] B. Bresar, S. Klavzar, D.F. Rail, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010), 979-991.
• [4] Cs. Bujtas, On the game domination number of graphs with given minimum degree, Electron. J. Combin. 22 (2015), #P3.29.
• [5] Cs. Bujtas, On the game total domination number, Graphs Combin. 34 (2018), 415-425.
• [6] Cs. Bujtas, P. Dokyeesun, V. Irsic, S. Klavzar, Connected domination game played on Cartesian products, Open Math. 17 (2019), 1269-1280.
• [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] P. Dorbec, M.A. Henning, Game total domination for cycles and paths, Discrete Appl. Math. 208 (2016), 7-18.
• [9] P. Dorbec, G. Kosmrlj, G. Renault, The domination game played on unions of graphs, Discrete Math. 338 (2015), 71-79.
• [10] R. Hammack, W. Imrich, S. Klavzar, Handbook of Product Graphs, 2nd ed., CRC Press, Boca Raton, FL, 2011.
• [11] M.A. Henning, S. Klavzar, D.F. Rall, Total version of the domination game, Graphs Combin. 31 (2015), 1453-1462.
• [12] M.A. Henning, S. Klavzar, D.F. Rail, The 4/5 upper bound on the game total domination number, Combinatorica 37 (2017), 223-251.
• [13] M.A. Henning, D.F. Rall, Progress towards the total domination game 3/4-conjecture, Discrete Math. 339 (2016), 2620-2627.
• [14] M.A. Henning, A. Yeo, Total Domination in Graphs, Springer Monographs in Mathematics, 2013.
• [15] V. Irsic, Effect of predomination and vertex removal on the game total domination number of a graph, Discrete Appl. Math. 257 (2019), 216-225.
• [16] V. Irsic, Connected domination game: predomination, Stal ler-start game, and lexicographic products, arXiv:1902.02087 [Math.CO] (6 Feb 2019).
• [17] T. James, S. Klavzar, A. Vijayakumar, The domination game on split graphs, Bull. Aust. Math. Soc. 99 (2019), 327-337.
• [18] W.B. Kinnersley, D.B. West, R. Zamani, Extremal problems for game domination number, SIAM J. Discrete Math. 27 (2013), 2090-2107.
• [19] S. Klavzar, D.F. Rall, Domination game and minimal edge cuts, Discrete Math. 342 (2019), 951-958.
• [20] K. Xu, X. Li, On domination game stable graphs and domination game edge-critical graphs, Discrete Appl. Math. 250 (2018), 47-56.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).