1. bookAHEAD OF PRINT
Detalles de la revista
License
Formato
Revista
eISSN
2083-5892
Primera edición
13 Apr 2013
Calendario de la edición
4 veces al año
Idiomas
Inglés
access type Acceso abierto

Domination Game: Effect of Edge Contraction and Edge Subdivision

Publicado en línea: 16 Dec 2020
Volumen & Edición: AHEAD OF PRINT
Páginas: -
Recibido: 27 Dec 2019
Aceptado: 28 Sep 2020
Detalles de la revista
License
Formato
Revista
eISSN
2083-5892
Primera edición
13 Apr 2013
Calendario de la edición
4 veces al año
Idiomas
Inglés
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-wAbierto 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.1899Abierto 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.025Abierto 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.025Abierto 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/100786800Abierto 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.014Abierto 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.015Abierto 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.022Abierto 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/4497Abierto 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.024Abierto 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/140976935Abierto 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_55Abierto 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/120884742Abierto 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.e93Abierto 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.017Abierto 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.027Abierto 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.024Abierto DOISearch in Google Scholar

Artículos recomendados de Trend MD

Planifique su conferencia remota con Sciendo