Geodesic
Domination Game: Extremal Families for the 3/5-Conjecture for Forests
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 2, pp. 369-381.

Voir la notice de l'article provenant de la source Library of Science

In the domination game on a graph G, the players Dominator and Staller alternately select vertices of G. Each vertex chosen must strictly increase the number of vertices dominated. This process eventually produces a dominating set of G; Dominator aims to minimize the size of this set, while Staller aims to maximize it. The size of the dominating set produced under optimal play is the game domination number of G, denoted by γ_g (G). Kinnersley, West and Zamani [SIAM J. Discrete Math. 27 (2013) 2090-2107] posted their 3/5-Conjecture that γ_g (G) ≤ 3/5 n for every isolate-free forest on n vertices. Brešar, Klavžar, Košmrlj and Rall [Discrete Appl. Math. 161 (2013) 1308-1316] presented a construction that yields an infinite family of trees that attain the conjectured 3/5-bound. In this paper, we provide a much larger, but simpler, construction of extremal trees. We conjecture that if G is an isolate-free forest on n vertices satisfying γ_g (G) = 3/5 n, then every component of G belongs to our construction.
Keywords: domination game, 3/5 conjecture 
@article{DMGT_2017_37_2_a4,
     author = {Henning, Michael A. and L\"owenstein, Christian},
     title = {Domination {Game:} {Extremal} {Families} for the {3/5-Conjecture} for {Forests}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {369--381},
     publisher = {mathdoc},
     volume = {37},
     number = {2},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a4/}
}
TY  - JOUR
AU  - Henning, Michael A.
AU  - Löwenstein, Christian
TI  - Domination Game: Extremal Families for the 3/5-Conjecture for Forests
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 369
EP  - 381
VL  - 37
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a4/
LA  - en
ID  - DMGT_2017_37_2_a4
ER  - 
%0 Journal Article
%A Henning, Michael A.
%A Löwenstein, Christian
%T Domination Game: Extremal Families for the 3/5-Conjecture for Forests
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 369-381
%V 37
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a4/
%G en
%F DMGT_2017_37_2_a4
Henning, Michael A.; Löwenstein, Christian. Domination Game: Extremal Families for the 3/5-Conjecture for Forests. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 2, pp. 369-381. http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a4/

[1] 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.015

[2] 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.014

[3] B. Brešar, S. Klavžar, G. Košmrlj and D.F. Rall, Domination game: extremal fam- ilies of graphs for the 3/5-conjectures, Discrete Appl. Math. 161 (2013) 1308-1316. doi: 10.1016/j.dam.2013.01.025

[4] B. Brešar, S. Klav҆žar und D. Rall, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010) 979-991. doi: 10.1137/100786800

[5] B. Brešar, S. Klavžar and D. Rall, Domination game played on trees and spanning subgraphs, Discrete Math. 313 (2013) 915-923. doi: 10.1016/j.disc.2013.01.014

[6] Cs. Bujtás, Domination game on trees without leaves at distance four, in: Proc. 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, A. Frank, A. Recski, G. Wiener, (Eds), June 4-7, 2013 (Veszprém, Hungary, 73-78).

[7] Cs. Bujtás, S. Klavžar and G. Košmrlj, Domination game critical graphs, Discuss. Math. Graph Theory 35 (2015) 781-796. doi: 10.7151/dmgt.1839

[8] 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.024

[9] 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/140976935

[10] M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics, 2013). `

[11] 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/120884742

[12] G. Košmrlj, Realizations of the game domination number, J. Comb. Optim. 28 (2014) 447-461. doi: 10.1007/s10878-012-9572-x