TY - JOUR
T1 - Domination game
T2 - A proof of the 3/5-conjecture for graphs with minimum degree at least two
AU - Henning, Michael A.
AU - Kinnersley, William B.
N1 - Publisher Copyright:
© 2016 Society for Industrial and Applied Mathematics.
PY - 2016
Y1 - 2016
N2 - 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). In this paper, we prove that γg(G) ≤ 2n/3 for every n-vertex isolate-free graph G. When G has minimum degree at least 2, we prove the stronger bound γg(G) ≤ 3n/5; this resolves a special case of a conjecture due to Kinnersley, West, and Zamani [SIAM J. Discrete Math., 27 (2013), pp. 2090-2107]. Finally, we prove that if G is an n-vertex isolate-free graph with l vertices of degree 1, then γg(G) ≤ 3n/5 + [l/2] + 1; in the course of establishing this result, we answer a question of Brešar et al. [Discrete Math., 330 (2014), pp. 1-10].
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). In this paper, we prove that γg(G) ≤ 2n/3 for every n-vertex isolate-free graph G. When G has minimum degree at least 2, we prove the stronger bound γg(G) ≤ 3n/5; this resolves a special case of a conjecture due to Kinnersley, West, and Zamani [SIAM J. Discrete Math., 27 (2013), pp. 2090-2107]. Finally, we prove that if G is an n-vertex isolate-free graph with l vertices of degree 1, then γg(G) ≤ 3n/5 + [l/2] + 1; in the course of establishing this result, we answer a question of Brešar et al. [Discrete Math., 330 (2014), pp. 1-10].
KW - Domination
KW - Domination game
KW - Game domination number
UR - http://www.scopus.com/inward/record.url?scp=84962146900&partnerID=8YFLogxK
U2 - 10.1137/140976935
DO - 10.1137/140976935
M3 - Article
AN - SCOPUS:84962146900
SN - 0895-4801
VL - 30
SP - 20
EP - 35
JO - SIAM Journal on Discrete Mathematics
JF - SIAM Journal on Discrete Mathematics
IS - 1
ER -