ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 13 (2017) 125-136
Domination game on paths and cycles
Gasper Kosmrlj *
AbeliumR&D d.o.o., Kajuhova ulica 90, Ljubljana, Slovenia
Received 10 July 2015, accepted 8 February 2017, published online 22 February 2017
Domination game is a game on a simple graph played by two players, Dominator and Staller who are alternating in taking turns. In each turn a player chooses a vertex in such a way that at least one new vertex gets dominated by this move. The game ends when all vertices are dominated, and thus no legal move is possible. As the names of the players suggest, Dominator tries to finish the game as fast as possible, while Staller wants to prolong its end as long as she can. By Yg (y'g) we denote the total number of moves in the game when Dominator (resp. Staller) starts, and both players play according to their optimal strategies. In a manuscript from 2012, Kinnersley et al. determined Yg and Yg' for paths and cycles, but have not yet published this very important result. In this paper we give an alternative proof for these formulas. Our approach also explicitly describes optimal strategies for both players.
Keywords: Domination game, game domination number, paths, cycles. Math. Subj. Class.: 05C57, 91A43, 05C69
1 Introduction
The Domination game is a game played on a simple graph G by two players, Dominator and Staller. They are alternating in choosing vertices from G such that in every move at least one new, previously undominated, vertex gets dominated. We say that a vertex is dominated if it is either chosen or is a neighboor of a chosen vertex. The game ends when all vertices of G are dominated, that is when the set of chosen vertices forms a dominating set of G. As the names of the players suggest, Dominator wants to finish the game in the least possible number of moves, while Staller's goal is just the opposite: to play the game as long as she can. A game when Dominator makes the first move will be called a D-game, while S-game will denote a game when Staller starts. The game domination number jg (G)
* The author acknowledges the project was financially supported by the Slovenian Research Agency under the grants P1-0297 and L7-5554.
E-mail address: gasperk@abelium.eu (Gasper Kosmrlj)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
126
Ars Math. Contemp. 13 (2017) 125-136
(Staller-start game domination number y'b (G)) denotes the total number of moves made in the D-game (resp. S-game) on G when both players play optimally.
Although the game was introduced not long ago by Bresar et al. in [4], it has already attracted several authors who have studied different aspects of the game, among which the most popular seems to be the so-called 3/5-conjecture posed by Kinnersley et al. in [14]. A major breakthrough was made by Bujtas in [5] by introducing a powerful greedy method for proving upper bounds of the game domination number. For other papers with results regarding the mentioned conjecture see [2,6,10]. Moreover, the greedy method has already been applied in [7] to improve upper bounds on the domination number of a graph.
Other topics of the domination game that were studied include computational complexity of the game (see [1, 16]), metric properties with respect to the domination game (see [3]), the domination game played on disjoint union (see [9]), realizations of the game domination numbers (see [17]), and characterizations (see [15, 18]). Also, the game has motivated studies of new games such as the total version of domination game, introduced and studied in [11, 12], and the disjoint domination game introduced by Bujtas and Tuza in [8].
In this paper we will study the domination game on paths and cycles. Kinnersley et al. have in [13] already found formulas for the game domination number of these graphs. Since these results are fundamental for the theory of the domination game, it is rather unfortunate that they are not published yet. Moreover, their proof is analytical and does not offer us much of an insight into the optimal strategies of both players. The latter will implicitly follow from our proof in the next section. In the rest of this section we introduce some notation and results needed in the new proofs of formulas for paths and cycles.
For a graph G and a subset of vertices S C V (G) we denote by G|S a partially dominated graph where the vertices of S are considered to be already dominated, and thus not need to be dominated in the course of the game. Note that S can be an arbitrary subset of V(G), and not only a union of closed neighborhoods of some vertices. From G|S we get the residual graph if we remove from G all edges between already dominated vertices, and all vertices v that cannot be chosen anymore, more precisely N [v] C S.
Theorem 1.1 (Continuation Principle, [14]). Let G be a graph and A, B C V(G). If B C A, then 7s(G|A) < 7s(G|B) and ig(G|A) < ig (G|B).
One of the corollaries of Continuation Principle is the fact that Yg and Yg never differ for more than one.
Theorem 1.2 ([4, 14]). For any graph G, Y (G) - ig (G)| < 1.
We say that a partially dominated graph G|S realizes a pair (k, £) G NxN if Yg (G|S) = k and y'9(G|S) = In the light of Theorem 1.2 we can now classify graphs into three different families, each of them realizing one of the possible pairs (k, k + 1), (k, k) and (k + 1, k). By PLUS we denote the family of all graphs that realize (k, k +1) for some positive k. Similarly we define EQUAL and MINUS. Lastly, we say that a graph is a no-minus graph if Yg(G|S) < ig(G|S) for every S C V(G).
Theorem 1.3 ([14]). Forests are no-minus graphs.
Some other families of no-minus graphs are given in [9], as well as the game domination numbers of the disjoint union of two no-minus graphs. If at least one of the components is an equal graph the following holds.
G. Kosmrlj: Domination game on paths and cycles
127
Theorem 1.4 ([9]). Let G1|S1 and G2|S2 be partially dominated no-minus graphs. If G1|S1 realizes (k, k) and G2|S2 realizes (t, m) (where m e {t, t + 1}), then the disjoint union (G1 U G2)|(S1 U S2) realizes (k + t, k + m).
In the second case, when both of the components are plus graphs we get the next result.
Theorem 1.5 ([9]). Let G1|S1 and G2|S2 be partially dominated no-minus graphs such that G1 |S1 realizes (k, k + 1) and G2 |S2 realizes (t, t +1). Then
k + t < ys((G1 U G2)|(S1 U S2)) < k + t +1,
k +1 + 1 < 7g((G1 u G2)|(S1 u S2)) < k +1 + 2. 2 Paths and cycles
The following formulas for the game domination number of paths and cycles were proved in [13]:
Yg (Pn) = Yg (Cn)
Yg (Pn) Yg (Cn)
In the course of the game on a path or on a cycle, we come across two special partially dominated paths. Let P^ denote a partially dominated path of order n+2 with both pendant vertices being already dominated, see Fig. 1. By Pn we denote a partially dominated path of order n + 1 where exactly one of the leaves is dominated, see Fig. 1 again. Note that in both cases n denotes the number of undominated vertices.
( \n 1 - 1; n = 3 (mod 4), | \n 1; otherwise, " n" 2 ,
f \n-11 - 1; n = 2 (mod 4), \ \n—11; otherwise.
-o.................o-o-•	•-a.................o-o
Figure 1: Partially dominated paths P^ (left) and Pn (right)
At first we prove the formulas for the game domination number of paths with both leaves dominated.
Lemma 2.1. For every n > 0, we have
\n 1 - 1; n = 3 (mod 4),
Yg (Pn)	\ \ § 1, otherwise,
V (P„) = i \21 +1, n = 2 (mod 4), 'g (Pn)	\ \n 1; otherwise.
Moreover, for every i, j > 0 such that i + j = n, ir = (i mod 4) and jr = (j mod 4), we
n
n
128
Ars Math. Contemp. 13 (2017) 125-136
also have
Yg (P'' U Pj'') =
Yg (P" U Pj')
Yg (P'') + Yg (Pj''); Yg (P'') + Yg (Pj'') + 1;
Yg (P'') + Yg (pj''); Yg (P'') + Yg (Pj'') + 1;
Yg (P'') + Yg (Pj'')+2;
(ir ,jr) e {0,1} X {0,1, 2, 3} U
{0,1, 2, 3} X {0,1}, (ir ,j) e {2, 3} X {2, 3},
(ir ,jr) e {0, 1} X {0, 1}, (ir jr) e {0, 1} X {2, 3} U
{2, 3} X {0,1} U {(2, 2)}, (ir,jr) e {(2, 3), (3, 2), (3, 3)}.
Proof. We prove all four formulas simultaneously by induction on the number of undomi-nated vertices n. It is easy to check by hand that all formulas hold for n < 8. Let us now assume that n > 9.
Let us first consider a D-game on P,'. Let u be one of the (dominated) leaves, v its (unique) neighbor and w the neighbor of v different from u. Since N[u] C N[v] C N[w] U {u} holds, using Continuation Principle we get that Yg(P^'^N[w] U {u})) < Yg(P''|N[v]) < Yg(P,"|N[u]), and thus we can assume that Dominator does not choose a leaf nor a leaf's neighbor in his first move on P,''. Hence we get that the residual graph after the first move is the disjoint union Pr'' U Ps'' where r, s > 0 and r + s = n — 3. More precisely, we get the following:
Yg (Pn) = 1 + min{Yg (P" U Ps") | r + s = n — 3, r, s > 0} .
-O-
o-
x
-o-
■o
P''
P''
Figure 2: Partially dominated path after Dominator choosing x on Pf
We now consider four cases regarding the value of n mod 4. By induction hypothesis we get that the following holds for every k > 2.
Yg (Pi'fc) = 1 + min {Yg (P^ U P^+i) | i + m + 1 = k, i, m > 0} U {Yg(P«+2 U P^m+3) | i + m + 2 = k, i, m > 0}
= 1 + min
{Yg(P«)+ Yg(PL+1) I i + m +1 = k, i,m > 0} U
{Yg (P«+2) + Yg (Pim+3) + 2 | i + m + 2 = k, i, m > 0}
1 + min
{2i + (2m + 1) | i + m + 1 = k, i, m > 0} U
{(2i + 1) + (2m + 1) + 2) | i + m + 2 = k, i, m > 0}
G. Kosmrlj: Domination game on paths and cycles
129
1 + min{2k - 1, 2k} = 2k,
Yg (P4fc+l) = 1 + min
{7g (P& u PL+2) I e + m +1 = k, e,m > 0} U
{7g(P£+! u P^m+i) I e + m + 1 = k, e, m > 0} U {Yg(P«+3 U P^+3) I e + m + 2 = k, e, m > 0} 1 + min{2k, 2k, 2k} = 2k +1,
Yg (P4fc+2) = 1 + min
{Yg(P& U Pi'm+3) I e + m + 1 = k, e, m > 0} U
{Yg(P£+i U Pim+2) I e + m + 1 = k, e, m > 0} 1 + min{2k, 2k + 1} = 2k + 1,
Yg (P4fc+3)
1 + min
{Yg(p£ UPim) I e + m = k, e,m > 0} U
{Yg(P£+i U P^+3) I e + m + 1 = k, e, m > 0} U {Yg(P«+2 U PL+2) I e + m + 1 = k, e, m > 0}
= 1 + min{2k, 2k + 1, 2k + 1} = 2k +1.
Similarly we compute the game domination number of P' of the S-game. Since the moves available are the same as those in the D-game, the set of possible residual graphs after Staller's first move is the same as above, that is P''_ 1, P,"_2, P^s or Pr'' U Ps'', where r, s > 1 and r + s = n - 3. By Continuation Principle, Staller either plays on a dominated vertex (which is a leaf) or chooses such a vertex x that the residual graph of P^'|N [x] has two components, both of which are paths with both of their leaves already dominated. Continuation Principle assures us that choosing the neighbor of a leaf or the vertex on a distance two from a leaf is never better for Staller than choosing a leaf. Using induction hypothesis the following holds for every k > 2.
yO (Pik )
1 + max
{Yg (Pi'(fc-i)+3 )}U
{Yg(P£ U PL+i) I e + m + 1 = k, e, m > 0} U {Yg(P«+2 U PL+3) I e + m + 2 = k, e, m > 0}
1 + max
{Yg (PVi)+3 )}U
{Yg(Pii) + Yg(PL+i) I e + m + 1 = k, e, m > 0} U {Yg (P&+2) + Yg (PL+3) + 1 I e + m + 2 = k, e, m > 0}
130
Ars Math. Contemp. 13 (2017) 125-136
1 + max
{2k - 1} U
{2i + (2m +1) | i + m + 1 = k, i, m > 0} U {(2i + 1) + (2m + 1) + 1 | i + m + 2 = k, i, m > 0} 1 + max{2k - 1, 2k - 1, 2k - 1} = 2k,
Yg (P'fc+i) = 1 + max
{Yg (Pk )}U
{Yg(P£ U Pim+2) | i + m +1 = k, i,m > 0} U {Yg(P«+i U Pm+i) | i + m + 1 = k, i, m > 0} U
{Yg (P«+3 U Pi'm+s) I i + m + 2 = k, i, m > 0} 1 + max{2k, 2k - 1, 2k, 2k - 1} = 2k + 1,
Yg (P4/C+2)
= 1 + max {Yg(Pi'fc+i)}U
{Yg(P£ U P^m+s) | i + m +1 = k, i, m > 0} U {Yg(P«+i U P^m+2) | i + m + 1 = k, i, m > 0} = 1 + max{2k + 1, 2k - 1, 2k} = 2k + 2,
Yg (Pi'fc+s)
= 1 + max
{Yg (Pi'fc+2)}U
{Yg(P& U P") | i + m = k, i, m > 0} U
{Yg(P«+1 U P^'m+s) | i + m + 1 = k, i, m > 0} U
{Yg(Pii+2 U Pim+2) | i + m + 1 = k, i, m > 0} = 1 + max{2k + 1, 2k, 2k, 2k + 1} = 2k + 2 .
Next we show the formulas for the game domination number of the disjoint union P/' U Pj'. From the first two formulas proven above we can quickly deduce that P^' is an EQUAL if and only if k = 0 (mod 4) or k = 1 (mod 4). In the other two cases we get that Pk' is a PLUS. Since paths are no-minus graphs, by Theorem 1.4 it follows that formulas hold when at least one of the components is an EQUAL.
It remains to prove the case when both components are PLUS. Let us assume first that i = 4i + 2 and j = 4m + 2, where i, m > 1. We would like to prove that Pzii+2 U Pz(m+2 realizes the pair (2i + 2m + 3,2i + 2m + 3). By Theorem 1.5 it follows that we only need to prove the lower bound for Yg and the upper bound for Yg' . For the former we need to prove that Staller can ensure that on P^i+2 U P,4m+2 at least 2m + 2i + 3 moves are played. Since we did not say anything about the relation between i and m we can without loss of generality assume that Dominator plays his first move in Pzii+2. Using Continuation Principle in the same way as above when proving the formula for Yg (P„), he has only two
G. Kosmrlj: Domination game on paths and cycles
131
conceptually different options for his move so that the residual graph of -P^+2 after this move is either P^ U Pi's+3 or P^+i U Pi's+2, where r + s = i - 1 and r, s > 0. If Staller then chooses a dominated leaf in the component with the odd number of undominated vertices, by induction hypothesis and by Theorem 1.4 we get the following.
Yg (P
4£+2
UP
4m+2
) = 1 + min
> 2 + min
j(P4r U Pis+3 U P4m+2)
4r + 1 U P4s+2 U P4m+2)
Yg (p
Yg (P4r U Pis+2 U Pim+2) Tg (P4r U P4s+2 U Pim+2)
= 2 + (Yg (Pi; ) + Yg (P4S+2) + Yg (Pim+2) + 1) = 2+(2r + (2s + 1) + (2m + 1) + 1) = 2+(2i +2m +1) = 2i + 2m + 3 .
Proof of the upper bound in the S-game follows similar lines. Staller has three conceptually different options for her first move, and then Dominator plays in the component with an odd number of undominated vertices such that he chooses a vertex at a distance 2 from a dominated leaf. By induction hypothesis and Theorem 1.4 we then get the following for
every r, s > 0, r + s = i - 1 .
Y
/Yg (P&+1 U Pim+2)	\
Yg (P«+2 U Pi'm+2) = 1 + max I Yg (P£ U Pi's+3 U P^+2 ) I
V	Yg (Pi'r+1 U Pi's+2 U Pim+2)/
(Y'g (P4(£-1)+2 U P4m+2 )	\
Yg (Pi; U Pi's U P4m+2^ I
Yg (P4(r-1) + 2 U P4s+2 U P4m+2) )
( Yg (P^-1)+2)+ Yg (Pim+2 ) + 1	\
= 2 + max I Yg (Pi'r) + Yg (P&) + Yg (Pim+2) + 1	I
V	Yg (Pi(;-1)+2) + Yg (Pi's+2) + Yg (Pim+2) + 2 J
/ (2(i - 1) + 1) + (2m +1) + 1	\
= 2 +max I 2r + 2s + (2m + 1) + 1	I
V	(2(r - 1) + 1) + (2s + 1) + (2m + 1) + 2 / = 2 + max{2i + 2m + 1, 2i + 2m, 2i + 2m + 1}
= 2i + 2m + 3 .
Finally, we prove that the disjoint unions P^+2 U Pim+3 and Pi;+3 U Pim+3 both realize the pair (2i + 2m + 3,2i + 2m + 4) for every i, m > 0. By Theorem 1.5 it is enough to prove the lower bound in the S-game presenting Staller's strategy. If she chooses a dominated leaf in Pim+3 in her first move, by the formulas proven above, we get that
Yg(P«+2 U Pim+3) > 1 + Yg(P«+2 U Pim+2) = 1 + 2i + 2m + 3 = 2i + 2m + 4 and from here also
Yg(Pi;+3 U Pim+3) > 1 + Yg(P«+3 U Pim+2) = 1 + 2i + 2m + 3 = 2i + 2m + 4 .
132
Ars Math. Contemp. 13 (2017) 125-136
This concludes the proof.
□
A direct corollary of the above lemma are formulas for the game domination number on cycles. Since cycles are vertex-transitive graphs any first move on a cycle leads to the same residual graph - a path with both leaves dominated.
Theorem 2.2. For every n > 3, we have
Yg (Cn) = Y'g (Cn) = Proof. By Lemma 2.1 it follows
rn]- 1; n = 3 (mod 4),
r n 1;
otherwise,
rn-T 1 - 1; n = 2 (mod 4),
r ^ 1;
otherwise.
Yg (Cn)
1+Yg (pn-3)
= 1 +
r1 +1; n - 3 = 2 (mod 4),
r1;
-1-
otherwise
rn-11 +1; n = 1 (mod 4), r n-11; otherwise
rn 1- 1; n = 3 (mod 4),
r n 1;
otherwise.
where we get the last equality by listing the values of both functions for n = 4k, 4k + 1,4k + 2,4k + 3 and k > 0. Similarly, using Lemma 2.1 again we get the Staller-start game domination number. For every n > 3, we get that
Yg (c„) = 1+Yg (pn- 3)
1+
r1- 1; n - 3 = 3 (mod 4), r1; otherwise
rnf11 - 1; n = 2 (mod 4), rn-211; otherwise.
□
The proof of Lemma 2.1 also gives us optimal strategies for both players. Choosing a vertex at a distance 2 from a dominated leaf is always optimal for Dominator, while playing on a dominated leaf in every move of the game is optimal for Staller. Since every residual graph of Pn that occurs during the game has at least one dominated leaf, both players can play in the same way as on Pn'. Hence the following lemma directly follows.
Lemma 2.3. For every n, m > 0, we have
Yg (Pn U Pm) = Yg (Pn' u Pm) = Yg (P^ U P^) and
Yg (Pn u Pm) = Yg (Pn' u Pm) = Yg (Pn' u Pm).
In particular, the last lemma says that Yg (Pn) = Yg (Pn) and Yg (Pn) = Yg (Pn) for every n > 0. Now everything is ready for the main theorem - the formulas for paths.
G. Kosmrlj: Domination game on paths and cycles
133
Theorem 2.4. For every n > 0, we have
Y g (Pn) l'g (Pn)
\n]- 1; n = 3 (mod 4), \n 1; otherwise,
2
Proof. We can easily check by hand that the assertion holds for n < 4. Let us now assume that n > 5. In the first move Dominator can either dominate two vertices by choosing one of the leaves, or three vertices by choosing any other vertex. By using Continuation Principle we can assume that Dominator never chooses a leaf. More precisely, choosing the leaf's neighbor can never be worse for Dominator than choosing a leaf. Hence, in his first move exactly three vertices are dominated, and the residual graph after this move is the disjoint union Pr' U Ps' where r, s > 0 and r + s = n - 3. We consider four cases regarding the value of n mod 4. In every case we first use the above argument about Dominator's first move, and then apply Lemma 2.3 and Lemma 2.1 to get the result for every k > 1.
Y g (P4 k) = 1+min
Yg (P4k+1)
{Yg (P4i U P4m+i) | t + m +1 = k, t,m > 0} U {Yg(PW2 U P4m+3) | t + m + 2 = k, t, m > 0} 1 + min
{Yg(P&+2 U P4m+3) | t + m + 2 = k, t, m > 0}
{Yg (P& U P4'm+i) | t + m + 1 = k, t, m > 0} U
1 + min
{2t + 2m +1 | t + m + 1 = k, t, m > 0} U
{2(t + m + 2) | t + m + 2 = k, t, m > 0} = 1 + min{2k - 1, 2k} = 2k,
1 + min
{Yg(P4* U P^m+2) | t + m +1 = k, t, m > 0} U
{Yg(P^+i U P4m+i) | t + m + 1 = k, t, m > 0} U
{Yg(P^+s U P4m+3) | t + m + 2 = k, t, m > 0} 1 + min{2k, 2k, 2k} = 2k +1,
Yg (P4k+2) = 1+min
{Yg(P4* U P^m+3) | t + m +1 = k, t, m > 0} U
n
{Yg(P4,+i U P4m+2) | t + m + 1 = k, t, m > 0} = 1 + min{2k, 2k + 1} = 2k + 1,
134
Ars Math. Contemp. 13 (2017) 125-136
Yg (P4fc+3)
1 + min
j7g(P4* U P4m) I e + m = k, e,m > 0} U
j7g(P^+i U P4m+3) I e + m + 1 = k, e, m > 0} U
j7g(P4,+2 U P4m+2) I e + m + 1 = k, e, m > 0}
= 1 + min{2k, 2k + 1, 2k + 1} = 2k +1.
We can see that Dominator's moves are similar to those in a game when one or two leafs are dominated. Since this is not the case in the S-game, we have to be more careful when considering moves of Staller on Pn. In the first move she clearly can not select a dominated leaf and dominate only one new vertex. Hence she either plays on a leaf and dominates two new vertices, or plays on a vertex of degree two, and thus splits the path into two (smaller) partially dominated paths. By using Lemma 2.3 and Lemma 2.1 we get the following for every k > 1 .
y: (P4fc)
1 + max
{Yg(P4(k-1)+2)} U
{Yg(P4* U P4m+i) I e + m + 1 = k, e, m > 0} U
{Yg(P4^+2 u P4m+3) I e + m + 2 = k, e, m > 0}
1 + max
{2k - 1}U
{2e + 2m + 1 I e + m + 1 = k, e, m > 0} U {2(e + m + 1) + 1 I e + m + 2 = k, e, m > 0} 1 + max{2k - 1, 2k - 1, 2k - 1} = 2k,
Y: (P4k+i) = 1 + max
{Yg(P4(k-i)+3)} U
{Yg (P4* U P4m+2) I e + m + 1 = k, e, m > 0} U {Yg(P4m U P4m+i) I e + m + 1 = k, e, m > 0} U
{Yg(P4^+3 u P4m+3) I e + m + 2 = k, e, m > 0}
1 + max{2k - 1, 2k - 1, 2k, 2k - 1} = 2k + 1,
Y: (P4fc+2) = 1 + max
{Yg (P4k )}U
{Yg (P4, U P4m+3) I e + m + 1 = k, e, m > 0} U {Yg(P4m U P4m+2) I e + m + 1 = k, e, m > 0}
1 + max{2k, 2k - 1, 2k} = 2k + 1,
G. Kosmrlj: Domination game on paths and cycles
135
Yg (Pfc+3)
1 + max
{Yg (Pfc+i)}U
|ys (P4* U PU | t + m = k, t, m > 0} U
{Yg(P-4£+i U Pim+s) | t + m + 1 = k, t, m > 0} U
{Yg(Pie+2 U Pim+2) | t + m + 1 = k, t, m > 0} 1 + max{2k + 1, 2k, 2k, 2k + 1} = 2k + 2 .
□
The last proof does not only give us the game domination number of paths, but also tells us what are the optimal moves of both players. We can see that choosing one of the leaves is an optimal first move of Staller on Pn when n ^ 1 (mod 4). In the case when n = 1 (mod 4) holds, Staller's optimal move is to play on a vertex v such that the residual graph obtained from Pn |N [v] consists of exactly two components Pr' and Ps', where r+s = n-3, r = 1 (mod 4) and s = 1 (mod 4).
References
[1]	B. Bresar, P. Dorbec, S. KlavZar and G. Kosmrlj, Complexity of the game domination problem, Theoret. Comput. Sci. 648 (2016), 1-7.
[2]	B. Bresar, S. KlavZar, G. Kosmrlj and D. F. Rall, Domination game: extremal families of graphs for the 3/5-conjectures, Discrete Appl. Math. 161 (2013), 1308-1316.
[3]	B. Bresar, S. KlavZar, G. Kosmrlj and D. F. Rall, Guarded subgraphs and the domination game, Discrete Math. Theor. Comput. Sci. 17 (2015), 161-168.
[4]	B. Bresar, S. KlavZar and D. F. Rall, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010), 979-991.
[5]	Cs. Bujtas, Domination game on forests, Discrete Math. 338 (2015) 2220-2228.
[6]	Cs. Bujtas, On the game domination number of graphs with given minimum degree, Electron. J. Combin. 22 (2015), Paper 3.29, 18 pp.
[7]	Cs. Bujtas and S. KlavZar, Improved upper bounds on the domination number of graphs with minimum degree at least five, Graphs Combin. 32 (2016), 511-519.
[8]	Cs. Bujtas and Z. Tuza, The disjoint domination game, Discrete Math. 339 (2016), 1985-1992.
[9]	P. Dorbec, G. Kosmrlj and G. Renault, The domination game played on unions of graphs, Discrete Math. 338 (2015), 71-79.
[10]	M. A. Henning and W. B. Kinnersley, Bounds on the game domination number, manuscript, 2014.
[11]	M. A. Henning, S. KlavZar and D. F. Rall, Total version of the domination game, Graphs Combin. 31 (2015), 1453-1462.
[12]	M. A. Henning, S. KlavZar and D. F. Rall, The 4/5 upper bound on the game total domination number, Combinatorica, to appear.
[13]	W. B. Kinnersley, D. B. West and R. Zamani, Game domination for grid-like graphs, manuscript, 2012.
[14]	W. B. Kinnersley, D. B. West and R. Zamani, Extremal problems for game domination number, SIAM J. Discrete Math. 27 (2013), 2090-2107.
136
Ars Math. Contemp. 13 (2017) 125-136
[15]	S. KlavZar, G. Kosmrlj and S. Schmidt, On graphs with small game domination number, Appl. Anal. Discrete Math. 10 (2016), 30-45.
[16]	S. KlavZar, G. Kosmrlj and S. Schmidt, On the computational complexity of the domination game, Iran. J. Math. Sci. Inform. 10(2) (2015), 115-122.
[17]	G. Kosmrlj, Realizations of the game domination number, J. Comb. Optim. 28 (2014), 447-461.
[18]	M. J. Nadjafi-Arani, M. Siggers and H. Soltani, Characterisation of forests with trivial game domination numbers, J. Comb. Optim. 32 (2016), 800-811.