Domination Game: Extremal Families for the 3/5-Conjecture for Forests

Michael A. Henning, and Christian Löwenstein. "Domination Game: Extremal Families for the 3/5-Conjecture for Forests." Discussiones Mathematicae Graph Theory 37.2 (2017): 369-381. <http://eudml.org/doc/288056>.

@article{MichaelA2017,
abstract = {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) ≤ ⅗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) = ⅗n, then every component of G belongs to our construction.},
author = {Michael A. Henning, Christian Löwenstein},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination game; 3/5 conjecture},
language = {eng},
number = {2},
pages = {369-381},
title = {Domination Game: Extremal Families for the 3/5-Conjecture for Forests},
url = {http://eudml.org/doc/288056},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Michael A. Henning
AU - Christian Löwenstein
TI - Domination Game: Extremal Families for the 3/5-Conjecture for Forests
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 2
SP - 369
EP - 381
AB - 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) ≤ ⅗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) = ⅗n, then every component of G belongs to our construction.
LA - eng
KW - domination game; 3/5 conjecture
UR - http://eudml.org/doc/288056
ER -