1. bookAHEAD OF PRINT
Dettagli della rivista
License
Formato
Rivista
eISSN
2083-5892
Prima pubblicazione
13 Apr 2013
Frequenza di pubblicazione
4 volte all'anno
Lingue
Inglese
access type Accesso libero

Domination Game: Effect of Edge Contraction and Edge Subdivision

Pubblicato online: 16 Dec 2020
Volume & Edizione: AHEAD OF PRINT
Pagine: -
Ricevuto: 27 Dec 2019
Accettato: 28 Sep 2020
Dettagli della rivista
License
Formato
Rivista
eISSN
2083-5892
Prima pubblicazione
13 Apr 2013
Frequenza di pubblicazione
4 volte all'anno
Lingue
Inglese
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-wApri 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.1899Apri 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.025Apri 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.025Apri 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/100786800Apri 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.014Apri 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.015Apri 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.022Apri 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/4497Apri 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.024Apri 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/140976935Apri 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_55Apri 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/120884742Apri 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.e93Apri 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.017Apri 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.027Apri 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.024Apri DOISearch in Google Scholar

Articoli consigliati da Trend MD

Pianifica la tua conferenza remota con Sciendo