1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Domination Game: Effect of Edge Contraction and Edge Subdivision

Published Online: 16 Dec 2020
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 27 Dec 2019
Accepted: 28 Sep 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

In this paper the behavior of the game domination number γg(G) and the Staller start game domination number γ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 γg(G) and γ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

MSC 2010

[1] 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. doi: 10.1007/s00010-019-00661-wOpen DOISearch in Google Scholar

[2] 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. doi: 10.7151/dmgt.1899Open DOISearch in Google Scholar

[3] 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. doi: 10.1016/j.tcs.2016.07.025Open DOISearch in Google Scholar

[4] 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. doi: 10.1016/j.dam.2013.01.025Open DOISearch in Google Scholar

[5] B. Brešar, S. Klavžar and D.F. Rall, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010) 979–991. doi: 10.1137/100786800Open DOISearch in Google Scholar

[6] B. Brešar, S. Klavžar and D.F. Rall, Domination game played on trees and spanning subgraphs, Discrete Math. 313 (2013) 915–923. doi: 10.1016/j.disc.2013.01.014Open DOISearch in Google Scholar

[7] 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. doi: 10.1016/j.disc.2014.04.015Open DOISearch in Google Scholar

[8] 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, G. Wiener (Ed(s)), (Veszprém, Hungary, June 4–7, 2013) 73–78.Search in Google Scholar

[9] Cs. Bujtás, Domination game on forests, Discrete Math. 338 (2015) 2220–2228. doi: 10.1016/j.disc.2015.05.022Open DOISearch in Google Scholar

[10] Cs. Bujtás, On the game domination number of graphs with given minimum degree, Electron. J. Combin. 22 (2015) #P3.29. doi: 10.37236/4497Open DOISearch in Google Scholar

[11] P. Dorbec, G. Košmrlj and G. Renault, The domination game played on unions of graphs, Discrete Math. 338 (2015) 71–79. doi: 10.1016/j.disc.2014.08.024Open DOISearch in Google Scholar

[12] 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. doi: 10.1137/140976935Open DOISearch in Google Scholar

[13] 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. doi: 10.1007/978-3-319-64419-6_55Open DOISearch in Google Scholar

[14] W.B. Kinnersley, D.B. West and R. Zamani, Extremal problems for game domination number, SIAM J. Discrete Math. 27 (2013) 2090–2107. doi: 10.1137/120884742Open DOISearch in Google Scholar

[15] G. Košmrlj, Domination game on paths and cycles, Ars Math. Contemp. 13 (2017) 125–136. doi: 10.26493/1855-3974.891.e93Open DOISearch in Google Scholar

[16] S. Schmidt, The 3/5-conjecture for weakly S(K1,3)-free forests, Discrete Math. 339(2016) 2767–2774. doi: 10.1016/j.disc.2016.05.017Open DOISearch in Google Scholar

[17] K. Xu and X. Li, On domination game stable graphs and domination game edge-critical graphs, Discrete Appl. Math. 250 (2018) 47–56. doi: 10.1016/j.dam.2018.05.027Open DOISearch in Google Scholar

[18] K. Xu, X. Li and S. Klavžar, On graphs with largest possible game domination number, Discrete Math. 341 (2018) 1768–1777. doi: 10.1016/j.disc.2017.10.024Open DOISearch in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo