1. bookAHEAD OF PRINT
Informacje o czasopiśmie
License
Format
Czasopismo
eISSN
2083-5892
Pierwsze wydanie
13 Apr 2013
Częstotliwość wydawania
4 razy w roku
Języki
Angielski
access type Otwarty dostęp

Domination Game: Effect of Edge Contraction and Edge Subdivision

Data publikacji: 16 Dec 2020
Tom & Zeszyt: AHEAD OF PRINT
Zakres stron: -
Otrzymano: 27 Dec 2019
Przyjęty: 28 Sep 2020
Informacje o czasopiśmie
License
Format
Czasopismo
eISSN
2083-5892
Pierwsze wydanie
13 Apr 2013
Częstotliwość wydawania
4 razy w roku
Języki
Angielski
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-wOtwórz 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.1899Otwórz 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.025Otwórz 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.025Otwórz 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/100786800Otwórz 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.014Otwórz 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.015Otwórz 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.022Otwórz 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/4497Otwórz 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.024Otwórz 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/140976935Otwórz 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_55Otwórz 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/120884742Otwórz 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.e93Otwórz 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.017Otwórz 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.027Otwórz 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.024Otwórz DOISearch in Google Scholar

Polecane artykuły z Trend MD

Zaplanuj zdalną konferencję ze Sciendo