1. bookAHEAD OF PRINT
Détails du magazine
License
Format
Magazine
eISSN
2083-5892
Première parution
13 Apr 2013
Périodicité
4 fois par an
Langues
Anglais
access type Accès libre

Domination Game: Effect of Edge Contraction and Edge Subdivision

Publié en ligne: 16 Dec 2020
Volume & Edition: AHEAD OF PRINT
Pages: -
Reçu: 27 Dec 2019
Accepté: 28 Sep 2020
Détails du magazine
License
Format
Magazine
eISSN
2083-5892
Première parution
13 Apr 2013
Périodicité
4 fois par an
Langues
Anglais
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-wOuvrir le 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.1899Ouvrir le 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.025Ouvrir le 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.025Ouvrir le 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/100786800Ouvrir le 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.014Ouvrir le 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.015Ouvrir le 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.022Ouvrir le 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/4497Ouvrir le 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.024Ouvrir le 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/140976935Ouvrir le 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_55Ouvrir le 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/120884742Ouvrir le 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.e93Ouvrir le 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.017Ouvrir le 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.027Ouvrir le 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.024Ouvrir le DOISearch in Google Scholar

Articles recommandés par Trend MD

Planifiez votre conférence à distance avec Sciendo