Article in volume
Authors:
Title:
Domination game: Effect of edge contraction and edge subdivision
PDFSource:
Discussiones Mathematicae Graph Theory 43(2) (2023) 313-329
Received: 2019-12-27 , Revised: 2020-09-18 , Accepted: 2020-09-28 , Available online: 2020-11-28 , https://doi.org/10.7151/dmgt.2378
Abstract:
In this paper the behavior of the game domination number $\gamma_g(G)$ and the
Staller start game domination number $\gamma_g'(G)$ by the contraction of an edge
and the subdivision of an edge are investigated. Here we prove that contracting
an edge can decrease $\gamma_g(G)$ and $\gamma_g'(G)$ by at most two, whereas
subdividing an edge can increase these parameters by at most two. In the case
of no-minus graphs it is proved that subdividing an edge can increase both these
parameters by at most one but on the other hand contracting an edge can decrease
these by two. All possible values of these parameters are also analysed here.
Keywords:
domination game, edge contraction, edge subdivision
References:
- B. Brešar, Cs. Bujtás, T. Gologranc, S. Klavžar, G. Košmrlj, T. Marc, B. Patkós, Zs. Tuza and M. Vizer, The variety of domination games, Aequationes Math. 93 (2019) 1085–1109.
https://doi.org/10.1007/s00010-019-00661-w - B. Brešar, P. Dorbec, S. Klavžar and G. Košmrlj, How long can one bluff in the domination game?, Discuss. Math. Graph Theory 37 (2017) 337–352.
https://doi.org/10.7151/dmgt.1899 - B. Brešar, P. Dorbec, S. Klavžar, G. Košmrlj and G. Renault, Complexity of the game domination problem, Theoret. Comput. Sci. 648 (2016) 1–7.
https://doi.org/10.1016/j.tcs.2016.07.025 - B. Brešar, S. Klavžar, G. Košmrlj and D.F. Rall, Domination game: Extremal families of graphs for the $3/5$-conjectures, Discrete Appl. Math. 161 (2013) 1308–1316.
https://doi.org/10.1016/j.dam.2013.01.025 - B. Brešar, S. Klavžar and D.F. Rall, Domination game and an imagination strategy, SIAM J.\ Discrete Math. 24 (2010) 979–991.
https://doi.org/10.1137/100786800 - B. Brešar, S. Klavžar and D.F. Rall, Domination game played on trees and spanning subgraphs, Discrete Math. 313 (2013) 915–923.
https://doi.org/10.1016/j.disc.2013.01.014 - B. Brešar, P. Dorbec, S. Klavžar and G. Košmrlj, Domination game: Effect of edge- and vertex-removal, Discrete Math. 330 (2014) 1–10.
https://doi.org/10.1016/j.disc.2014.04.015 - Cs. Bujtás, Domination game on trees without leaves at distance four, in: Proceedings of the 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, A. Frank, A. Recski and G. Wiener (Ed(s)), (Veszprém, Hungary June 4–7, 2013) 73–78.
- Cs. Bujtás, Domination game on forests, Discrete Math. 338 (2015) 2220–2228.
https://doi.org/10.1016/j.disc.2015.05.022 - Cs. Bujtás, On the game domination number of graphs with given minimum degree, Electron. J. Combin. 22 (2015) #P3.29.
https://doi.org/10.37236/4497 - P. Dorbec, G. Košmrlj and G. Renault, The domination game played on unions of graphs, Discrete Math. 338 (2015) 71–79.
https://doi.org/10.1016/j.disc.2014.08.024 - M.A. Henning and W.B. Kinnersley, Domination game: A proof of the $3/5$-conjecture for graphs with minimum degree at least two, SIAM J. Discrete Math. 30 (2016) 20–35.
https://doi.org/10.1137/140976935 - T. James, P. Dorbec and A. Vijayakumar, Further progress on the heredity of the game domination number, Lecture Notes in Comput. Sci. 10398 (2017) 435–444.
https://doi.org/10.1007/978-3-319-64419-6_55 - W.B. Kinnersley, D.B. West and R. Zamani, Extremal problems for game domination number, SIAM J. Discrete Math. 27 (2013) 2090–2107.
https://doi.org/10.1137/120884742 - G. Košmrlj, Domination game on paths and cycles, Ars Math. Contemp. 13 (2017) 125–136.
https://doi.org/10.26493/1855-3974.891.e93 - S. Schmidt, The $3/5$-conjecture for weakly $S(K_{1,3})$-free forests, Discrete Math. 339 (2016) 2767–2774.
https://doi.org/10.1016/j.disc.2016.05.017 - K. Xu and X. Li, On domination game stable graphs and domination game edge-critical graphs, Discrete Appl. Math. 250 (2018) 47–56.
https://doi.org/10.1016/j.dam.2018.05.027 - K. Xu, X. Li and S. Klavžar, On graphs with largest possible game domination number, Discrete Math. 341 (2018) 1768–1777.
https://doi.org/10.1016/j.disc.2017.10.024
Close