IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 52 (2014), 1195
ISSN 2232-2094
TOTAL DOMINATION GAME PLAYED IN FORESTS
Michael A. Henning Sandi Klavžar Douglas F. Rail
Ljubljana, March 6, 2014
Total Domination Game Played in Forests
o
Michael A. Henning a Sandi Klavzar b'c'd Douglas F. Rail e
m
o Ö
00 CSF CSF
u
CD CO
a
CD U
a Department of Mathematics, University of Johannesburg, South Africa
mahenning@uj.ac.za
b Faculty of Mathematics and Physics, University of Ljubljana, Slovenia Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia d Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia sandi.klavzar@fmf.uni-lj.si
Department of Mathematics, Furman University, Greenville, SC, USA doug.rall@furman.edu
Abstract
The recently introduced total domination game is studied. This game is played on a graph G by two players, named Dominator and Staller. They alternately take turns choosing vertices of G such that each chosen vertex totally dominates at least one vertex not totally dominated by the vertices previously chosen. Dominator's goal is to totally dominate the graph as fast as possible, and Staller wishes to delay the process as much as possible. The game total domination number, 7tg (G), of G is the number of vertices chosen when Dominator starts the game and both players play optimally. The Staller-start game total domination number, 7'tg (G), of G is the number of vertices chosen when Staller starts the game and both players play optimally. In this paper it is proved that if F is a forest on n vertices in which every component contains at least three vertices, then jtg (F) < 4n/5 and Yt'g(F) < (4n + 2)/5. As a consequence of this result, we obtain upper bounds for both games played on any forest that has no isolated vertices.
Key words: domination game; total domination game; game total domination number; forests
AMS Subj. Class: 05C57, 05C05, 91A43, 05C69
c
e
1 Introduction
CM
The domination game in graphs was introduced in [2] and extensively studied afterwards in [1, 2, 3, 5, 10, 11, 12, 13] and elsewhere. A vertex u in a graph G dominates a vertex v if u = v or u is adjacent to v in G. A dominating set of G is a set S of vertices of G such that every vertex in G is dominated by a vertex in S. The game played on a graph G consists of two players, Dominator and Staller, who take turns choosing a vertex from G. Each vertex chosen must dominate at least one vertex not dominated by the vertices previously chosen. The game ends when the set of vertices chosen becomes a dominating set in G. Dominator wishes to dominate the graph as fast as possible, and Staller wishes to delay the process as much as possible. The game domination number (resp. Staller-start game domination number), Yg(G) (resp. Yg (G)), of G is the number of vertices chosen when Dominator (resp. Staller) starts the game and both players play optimally.
Recently, the total version of the domination game was investigated in [8], where in particular it was demonstrated that these two versions differ significantly. A vertex u in a graph G totally dominates a vertex v if u is adjacent to v in G. A total dominating set of G is a set S of vertices of G such that every vertex of G is totally dominated by a vertex in S. The total domination game, played on a graph G again consists of two players called Dominator and Staller who take turns choosing a vertex from G. In this version of the game, each vertex chosen must totally dominate at least one vertex not totally dominated by the set of vertices previously chosen. At any particular point in the game some subset C of vertices has been chosen by the players, and it is the turn of one of the two players. We say that a vertex v of G is playable if v has a neighbor that is not totally dominated by C. If the player chooses v, then we say the player played v and we refer to this choice as the move of that player. For emphasis we may also say it was a legal move. The game ends when the set of vertices chosen is a total dominating set in G, or equivalently when G has no playable vertices. Dominator wishes to totally dominate the graph as fast as possible, and Staller wishes to delay the process as much as possible.
The game total domination number, Ytg (G), of G is the number of vertices chosen when Dominator starts the game and both players play optimally. The Staller-start game total domination number, Ytg (G), of G is the number of vertices chosen when Staller starts the game and both players play optimally. For simplicity, we shall refer to the Dominator-start total domination game and the Staller-start total domination game as Game 1 and Game 2, respectively.
A partially total dominated graph is a graph together with a declaration that some vertices are already totally dominated; that is, they need not be totally dominated in the rest of the game. In [8], the authors present a key lemma, named the Total Continuation Principle, which in particular implies that the number of moves in Game 1 and Game 2 when played optimally can differ by at most 1.
a
CD	2
2
vO
lO
o
I
CM 00 CM CM

CM
r
vD
For notation and graph theory terminology not defined herein, we in general follow [7]. We denote the degree of a vertex v in a graph G by dG(v), or simply by d(v) if the graph G is clear from the context. A leaf in a forest is a vertex of degree 1 in the forest. If X and Y are subsets of vertices in a graph G, then the set X totally dominates the set Y in G if every vertex of Y is adjacent to at least one vertex of X. In particular, if X totally dominates the vertex set V(G) of G, then X is a total dominating set in G. For more information on total domination in graphs see the recent book [9]. Since an isolated vertex in a graph cannot be totally dominated by definition, all graphs considered will be without isolated vertices.
Our aim in this paper is to establish upper bounds on the Dominator-start total domination game and the Staller-start total domination game played in a forest. More precisely, we shall prove the following result.
CO
u
a
CD U
Theorem 1 Let F be a forest on n vertices in which every component contains at least three vertices. Then,
o
Ytg (F) < 4n and ^ (F) < ^ 2
O
CM
Our proof strategy is to modify an ingenious approach adopted by Csilla Bujtas [5] who proved the 3/5-conjecture for the ordinary game domination number for the class of forests in which no two leaves are at distance 4 apart. Her approach is to color the vertices of a forest with three colors that reflect three different types of vertices and to associate a weight with each vertex. In the total version of the CM domination game, we modify Bujtas's approach by coloring the vertices of a forest with four colors that reflect four different types of vertices. In the next section we introduce this coloring and deduce its basic properties. In Section 3 we assign S weights to colored vertices and study the decrease of total weight of the forest as a consequence of playing vertices in the course of the game. In the subsequent section we define and study three phases of the game, while in Section 5 we describe and analyze a strategy of Dominator based on the three phases. The efforts of previous sections are culminated in Section 6 where a proof of Theorem 1 is given. As a consequence, we then prove that when F is a forest of order n with k components of order 2 and no isolated vertices, ytg(F) < 4n+2k and Ytg(F) < 4ra+2fc+2. Finally, we pose a so-called |-Conjecture.
• 1
2 A Residual Forest
CD
We consider the total domination game played on a forest F in which every component contains at least three vertices. At any stage of the game, let D denote the set of vertices played to date where initially D = 0. We define a colored-forest with

respect to the played vertices in the set D as a forest in which every vertex is colored with one of four colors, namely white, green, blue, or red, according to the following rules.
• A vertex is colored white if it is not totally dominated by D and does not
o u

I
CM 00 CM
£ CO CO
belong to D.
A vertex is colored green if it is not totally dominated by D but belongs to D.
• A vertex is colored blue if it is totally dominated by D but has a neighbor not totally dominated by D.
A vertex is colored red if it and all its neighbors are totally dominated by D.
Note that a vertex u is colored white if and only if D n N[u] = 0 and is colored green if and only if D n N[u] = {u}, where N[u] is the closed neighborhood of u.
We remark that in a partially total dominated forest the only playable vertices are those that have a white or green neighbor since a played vertex must totally dominate at least one new vertex. In particular, no red or green vertex is playable. Further, the status of a red vertex remains unchanged as the game progresses. Hence, once a vertex is colored red, it plays no role in the remainder of the game and can be deleted from the partially total dominated forest. Moreover since blue vertices are already totally dominated, an edge joining two blue vertices plays no role in the game, and can be deleted. Therefore in what follows, we may assume a partially total dominated forest contains no red vertices and has no edge joining two blue vertices. Adopting the terminology in [10], we call the resulting forest a residual forest.
Suppose that a residual forest contains a P2-component, H. Since we are assuming that every component of the original forest F contains at least three vertices, at least one vertex, say v, of H has degree at least 2 in the original forest F. Let w be a neighbor of v that is not in H. When a move was made earlier in the game and the edge vw was removed it is the case that either the vertex w was red and was deleted or both v and w were blue. In both cases v is colored blue in H. Hence, every P2-component in the residual forest consists of one blue vertex and either one white or one green vertex. The following additional properties of the residual forest
CO
follow readily from the properties of the coloring of the vertices.
CD
Observation 2 The following properties hold in a residual forest.
(a)	Every playable vertex has a white or green neighbor.
(b)	Every neighbor of a white vertex is a white or blue vertex.
(c)	Every neighbor of a green vertex is a blue vertex.
(d)	Every neighbor of a blue vertex is a white or green vertex.
a
K	4
vo
o u
Ctf
10
0 Ö
o
CM
1
CM CO CM CM
£ CO CO
CO CD
$H
CD CO
$H
a
CD U
(e)	Every playable vertex is a white or blue vertex.
(f)	There is no isolated vertex.
(g)	Every P2-component consists of one blue vertex and either one white or one green vertex.
3 The Assignment of Vertex Weights
We next associate a weight with every vertex in the residual forest as follows:
Color of vertex	Weight of vertex
white	4
green	3
blue	2
red	0
Table 1. The weights of vertices according to their color.
Since the residual forest by definition contains no red vertex, the above assignment of weight 0 to red vertices seems redundant. However, in due course of the game new red vertices are created and at that moment we assign them weight 0.
We define the weight of the residual forest F as the sum of the weights of the vertices in F and denote this weight by w(F). Hence each white vertex contributes 4 to the sum w(F), while each green and blue vertex contributes 3 and 2, respectively, to the sum w(F).
3.1 Types of Playable Vertices
Let v be a playable vertex in F. As observed earlier, the vertex v is white or blue, and has a white or green neighbor. We distinguish eight different legal moves in the residual forest F according to the following types.
Type 1: v is colored white and has at least two white neighbors.
Type 2: v is colored white and has exactly one white neighbor.
Type 3: v is colored blue and has degree at least 3.
Type 4: v is colored blue and has degree 2 with two white neighbors.
Type 5: v is colored blue and has degree 2 with one white and one green neighbor.
Type 6: v is colored blue and has degree 2 with two green neighbors.
Type 7: v is a blue leaf with a green neighbor.
Type 8: v is a blue leaf with a white neighbor.
vo
o u
10
0 o
CM
1
CM CO CM CM
£ CO CO
m
CD
$H
CD
m
u
a
CD U
Suppose that the playable vertex v is colored white. When v is played its color status changes from white to green. Further, each white neighbor of v changes status from white to blue, while each blue neighbor of v retains its color status. Hence if v is a type-1 vertex with k white neighbors, then when v is played the weight of F decreases by 1 + 2k, which is at least 5. Suppose that v is a type-2 vertex. Let w denote the white neighbor of v. By Observation 2(g), we know that the component containing v contains at least three vertices. When v is played, its status changes from white to green, while the status of w changes from white to blue. Hence, when v is played the weight of F decreases by at least 3. Each blue neighbor of v retains its color status. The status of every blue neighbor of w, if any, remains unchanged (colored blue) or changes from blue to red, while the status of every white neighbor of w different from v remains unchanged. Therefore, when v is played the weight of F decreases by exactly 3 or by at least 5.
Suppose that v is colored blue. When v is played its color status changes from blue to red. Further, each white neighbor of v changes status from white to blue or red, while each green neighbor of v changes status from green to red. Hence if v is a type-3 vertex with k white neighbors and £ green neighbors, where k + £ = d(v) > 3, then when v is played the weight of F decreases by at least 2 + 2k + 3£ and 2 + 2k + 3£ > 2 + 2d(v) > 8. If v is a type-4, type-5, or type-6 vertex, then when v is played the weight of F decreases by at least 6, 7 or 8, respectively. If v is a type-7 vertex and w denotes its green neighbor, then when v is played both v and w change status to red. Further, if d(w) > 2, then the color of every blue neighbor of w different from v either remains unchanged or changes to red. Therefore, the weight of F decreases by at least 5 in this case. Suppose v is a type-8 vertex and w denotes its white neighbor. If w has no white neighbor (this includes the case when w is a leaf), then when v is played both v and w are recolored red, implying that the weight of F decreases by at least 6. If w has a white neighbor, then when v is played v is recolored red and w is recolored blue, implying that the weight of F decreases by at least 4 in this case.
The decrease in the weight of F according to the different types of playable vertices is summarized in Table 2.
Type of playable vertex	Decrease in weight of F
Type-1	> 5
Type-2	3 or > 5
Type-3	> 8
Type-4	> 6
Type-5	> 7
Type-6	> 8
Type-7	> 5
Type-8	> 4
Table 2. The decrease in weight when playing different types of vertices.
We therefore have the following observation.
CM
vo
Observation 3 A played vertex in a residual forest decreases the weight by at least 3.
A
o
The following lemmas will prove to be useful.
Lemma 4 If the game is not yet over, then there exists a legal move that decreases the weight by at least 5.
lO
Proof. Suppose to the contrary that every legal move decreases the weight by at most 4. By Observation 3, every playable vertex in the residual forest F either decreases the weight by 3 or by 4. By Table 2, if a playable vertex decreases the weight by 3, then it is a type-2 vertex; if it decreases the weight by 4, then it is a type-8 vertex. Thus every white vertex has at most one white neighbor, and every blue vertex is a leaf with a white neighbor. By Observation 2(c), F has no green vertices and consequently F contains only white and blue vertices.
Suppose that F contains a blue vertex, v. As observed earlier, v is a leaf with a white neighbor, say w. If every neighbor of w is a blue vertex, then playing v decreases the weight by at least 6, a contradiction. Hence the vertex w has a white neighbor x. This implies that playing x decreases the weight by at least 5, which is a contradiction. Hence F contains only white vertices. By Observation 2(f) and 2(g), F contains at least three vertices. Hence there exists a white vertex with at least
CM
two white neighbors, a possibility ruled out in the first paragraph.	□
£ CO
Lemma 5 If a played vertex in a residual forest is a white vertex, then the resulting total decrease in weight is odd.
Proof. Let v be a white vertex in the residual forest F and suppose that v is playable. When v is played, its status changes from white to green; this contributes 1 to the decrease in weight of F. Every white neighbor of v changes status from white to blue and contributes 2 to the decrease in weight of F. Every blue neighbor of a white neighbor of v, if any, retains its blue color status or changes status from blue to red and therefore contributes either 0 or 2 to the decrease in weight of F. All other vertices retains their color status and contribute 0 to the decrease in weight of F. Therefore, when v is played the resulting total decrease in weight of F is odd. □
CO
o
CM
i
u
a
CD U
4 The Three Phases of the Game
CM
vO
O
CO CO
Before any move of Dominator, the game is in one of the following three phases.
•	Phase 1, if there exists a legal move that decreases the weight by at least 7.
•	Phase 2, if every legal move decreases the weight by at most 6, and there exists a legal move that decreases the weight by 6.
•	Phase 3, if every legal move decreases the weight by at most 5.
in
By Lemma 4, if the game is in Phase 3, then there exists a legal move that decreases the weight by 5.
We remark that it is possible for a game to be in Phase 2 and later again in Phase 1. Further, it is possible for a game to be in Phase 3 and later in Phase 1 or Phase 2.
4.1 Phase 3
As a consequence of our discussion in Section 3 that is summarized in Table 2, we have the following observation.
CM
Observation 6 If the game is in Phase 3, then the following hold in the residual forest.
(a)	Every white vertex has at most two white neighbors.
(b)	Every blue vertex is a leaf.
(c)	A green vertex, if it exists, is a leaf with a blue (leaf) neighbor.
(d)	A white vertex with a blue (leaf) neighbor has at least one white neighbor.
(e)	A white vertex has at most one blue (leaf) neighbor.
We are now in a position to prove the following structural lemma.
Lemma 7 If the game is in Phase 3 and T is any component of the residual forest, then one of the following holds.
(a)	T = P2, with one green vertex and one blue vertex.
(b)	T = P3, with a blue leaf and two white vertices.
(c)	T = P4, with two blue leaves and two white (central) vertices.
(d)	T = K\,3, with a blue leaf and three white vertices.
(e)	T = Pk, where k > 3, consisting entirely of white vertices.
Proof. Let T be a component of the residual forest as described in the statement of the lemma. If T contains a green vertex, then by Observation 6(c) we have that
a
K	8
vo
o u
10
0 o
CM
1
CM CO CM CM
£ CO CO
m
CD
$H
CD
m
T satisfies condition (a) in the statement of the lemma. Hence we may assume that T contains no green vertex.
Suppose that T contains a blue vertex, v. By Observation 6(b), the vertex v is a leaf. Let w be the neighbor of v. By assumption, w is a white vertex. By Observation 6(b) and 6(e), the vertex v is the only blue neighbor of w. By Observation 6(d), the vertex w has a white neighbor, say x. If T = P3, then T satisfies condition (b) in the statement of the lemma. Hence we may assume that T = P3. If x has two white neighbors, then playing x decreases the weight of T by at least 7 (note that after playing x, the vertex v becomes red), contradicting the fact that we are in Phase 3. Hence, w is the only white neighbor of x. If d(x) > 2, then by Observation 6(e), d(x) = 2 and x has a blue leaf neighbor. Analogously in this case, d(w) = 2. Thus if d(x) > 2, then T = P4 and T satisfies condition (c) in the statement of the lemma. Hence we may assume that x is a leaf. Since T = P3, our earlier observations imply that d(w) = 3 and w has a white neighbor, say z, different from x. If z has a blue (leaf) neighbor, then playing w decreases the weight of T by at least 7, a contradiction. If z has a white neighbor different from w, then playing z decreases the weight of T by at least 7, a contradiction. Therefore, z is a leaf, implying that T = K\,3 and T satisfies condition (d) in the statement of the lemma.
Hence, we may assume that T contains no blue vertex, for otherwise T satisfies condition (a), (b), (c), or (d) in the statement of the lemma. However, in this case, by Observation 6(a) we have that T satisfies condition (e) in the statement of the lemma.	□
By Lemma 7, if the game is in Phase 3, then a component of the residual forest can have one of five possible structures, which are illustrated in Figure 1.
I
B W W
B W W B
B
(a) (b) (c)
'WN W W
(d)
W 'W W
!w
(e)
Figure 1: Five possible components of the residual forest in Phase 3.
U
a
CD U
4.2 Phase 2
As a consequence of our discussion in Section 3 that is summarized in Table 2, we vO have the following observation.
o
Observation 8 Suppose it is Dominator's turn and every legal move decreases the weight by at most 6. The following hold in the residual forest.
(a)	Every white vertex has at most two white neighbors.
(b)	Every blue vertex is a leaf or has degree 2 with two white neighbors.
(c)	A green vertex, if it exists, is a leaf with a blue (leaf) neighbor.
in
GÏ
fi
GÏ O
CM
i
CM 00 CM CM
CO CO
CO CD
We are now in a position to prove the following structural lemmas.
Lemma 9 Suppose the game is in Phase 2. If T is a component of the residual forest and contains a playable vertex that decreases the weight by 6, then T has the following properties.
(a)	A playable vertex that decreases the weight by 6 is a blue vertex.
(b)	T only contains blue and white vertices, and contains at least one blue vertex.
(c)	A blue vertex of degree 2 in T has two white neighbors, both of which have at least one white neighbor.
Proof. Let T be as defined in the statement of the lemma. By Observation 2(e), every playable vertex is a white or blue vertex. By Lemma 5, a playable vertex in T that decreases the weight by 6 cannot be a white vertex, and is therefore a blue vertex. This establishes property (a). By Observation 8(b), every blue vertex is a leaf or has degree 2 with two white neighbors.
If T contains a green vertex, then by Observation 8(c) it follows that T is a P2 with one blue vertex and one green vertex. However, such a colored component does not have a playable vertex that decreases the weight by 6. Consequently, T only contains blue and white vertices, and by property (a) it has at least one blue vertex. This establishes property (b).
Let v be a blue vertex of degree 2 in T. By Observation 8(b), both neighbors of v are white vertices. If either of these two white vertices is adjacent only to blue vertices, then when v is played the resulting total decrease in weight is at least 8, a contradiction. Hence both neighbors of v are adjacent to white vertices. This establishes property (c).	□
CO
Lemma 10 Suppose the game is in Phase 2. Let T be a component of the residual forest that contains a playable vertex that decreases the weight by 6. If T has a blue leaf, v, with a (white) neighbor, w, that is not a leaf, then the following hold.
(a) d(w) =2 or d(w) = 3.
CD
m
u
a
CD U
(b)	Every vertex at distance 2 from v is a white vertex.
(c)	At least one neighbor of w has degree at least 2.
(d)	Every vertex at distance 3 from v is a blue vertex of degree 2.
A
Proof. Suppose that T contains a blue leaf, v, whose (white) neighbor w is not a leaf. If every neighbor of w is a blue vertex, then playing an arbitrary neighbor of w different from v decreases the weight by at least 8, a contradiction. Hence, w has at least one white neighbor, say x.
Suppose firstly that d(w) = 2. If x is a leaf, then T = P3 with one blue leaf and two white vertices. However, playing the blue vertex decreases the weight by 4, a contradiction. Hence, d(x) > 2. If x has a white neighbor different from w, then playing x decreases the weight by at least 7, a contradiction. Hence every neighbor of x different from w is a blue vertex.
o
Suppose that x has a (blue) leaf neighbor, say yi. If d(x) = 2, then T = P4 with two blue leaves and two white central vertices. Playing a blue vertex decreases the weight by 4, a contradiction with Lemma 9(a). Hence, d(x) > 3. Let y2 be a (blue) neighbor of x different from y1 and w. If y2 is a leaf, then playing w decreases the weight by at least 7, a contradiction. Hence, by Observation 8(b), d(y2) = 2
CM
and y2 has two white neighbors. Playing y2 decreases the weight by at least 8, a contradiction. Therefore, every neighbor of x different from w is a blue vertex of degree 2. Hence if d(w) = 2, then properties (a), (b), (c), and (d) all hold, as desired.
CM
Hence we may assume that d(w) > 3, for otherwise the lemma holds. Let y be a
CM neighbor of w different from v and x. Suppose that y is a blue vertex. If y is a leaf, then playing x decreases the weight by at least 7, a contradiction. Hence, d(y) = 2 and y has two white neighbors. Now playing y decreases the weight by at least 8, S a contradiction. Therefore, y is a white vertex, implying by Observation 8(a) that d(w) = 3. In particular, we note that properties (a) and (b) hold.
If both x and y are leaves, then T is a star K1,3 with one blue leaf and three white vertices. However, such a colored component does not have a playable vertex that decreases the weight by 6, contradicting our assumption about T. In particular, we note that property (c) holds. Renaming x and y if necessary, we may assume that d(x) > 2.
If x has a white neighbor different from w, then playing x decreases the weight by at least 7, a contradiction. If x has a blue leaf neighbor, then playing w decreases the weight by at least 7, a contradiction. Therefore, every neighbor of x different from w is a blue vertex of degree 2. Analogously, if d(y) > 2, then every neighbor of y different from w is a blue vertex of degree 2. In particular, we note that property (d) holds.	□
vo
o u
10
0 o
CM
1
CM CO CM CM
£ CO CO
m
CD
$H
CD
m
u
a
CD U
Suppose the game is in Phase 2 and T is a component of the residual forest that contains a playable vertex that decreases the weight by 6. Suppose further that T contains a blue leaf. Either T = P2 where T has one white vertex and one blue vertex or T has the structure described in Lemma 10. In the latter case T contains at least one of the four subgraphs that are illustrated in Figure 2, where the degrees of the darkened vertices are their exact degrees in the tree T, but where the degrees of the circled vertices may possibly be larger in the tree T. In addition, any white vertex at distance 2 from the blue leaf has exactly one white neighbor. Its other neighbor or neighbors (at distance 3 from the blue leaf) are blue vertices of degree 2 as shown in Figure 2.
B W
I
(a)
B < W<
WO
B 1 W< Wc (b)
B
W B W W
A
B W
W W' B W' W'
B W W
W
(c)
(d)
Figure 2: Subgraphs of a component of the residual forest in Phase 2.
5 Strategy of Dominator
We present in this section a strategy for Dominator playing in a residual forest F. The strategy of Dominator is to make sure that on average the weight decrease resulting from each played vertex in the game is at least 5.
If the game is always in Phase 1, then this is readily achieved since each move of Dominator decreases the weight by at least 7 while each move of Staller decreases the weight by at least 3. Hence since Dominator plays the first move, if 2k moves were played when the game is completed, then the total decrease in weight is at least 7k + 3k, while if 2k +1 moves are played when the game is completed, then the total decrease in weight is at least 7(k + 1) + 3k. In both cases, the average weight decrease for each move played is at least 5. We may therefore assume that the game is not always in Phase 1, and therefore that the game enters Phase 2 or Phase 3 at some stage.
As an immediate consequence of Lemma 7, Lemma 9, and Lemma 10, we have the following structural result.

CM
r
vD
Lemma 11 If the game is not in Phase 1, then an arbitrary component T of the residual forest has one of the following structures:
(a)	T has one of the five possible structures illustrated in Figure 1.
(b)	T has a subgraph that is one of the four possible subgraphs illustrated in Figure 2.
(c)	T has the following structure:
(i)	T contains only blue and white vertices, with at least one blue vertex.
(ii)	Every white vertex has at most two white neighbors.
(iii)	Every blue vertex has degree 2 with two white neighbors, each of which has at least one white neighbor.
Dominator's strategy is as follows. Suppose that the game is not in Phase 1 and it is Dominator's turn. If the move of Dominator completes the game, then by Lemma 11 the residual forest was a tree with the structure shown in either Figure 1(a) or Figure 2(a). In both cases, the decrease in weight is at least 5. Hence we may assume that the move of Dominator does not complete the game.
Dominator's initial strategy is to find a sequence of moves mi,..., mk starting with his first move, mi, and with moves alternating between Dominator and Staller such that if wi denotes the decrease in weight after move mi is played, then
J^Wi > 5k,	(1)
i=i
where either k is odd and the game is completed after move mk or k is even (and the game may or may not be completed after move mk). Further each move of Dominator is chosen to decrease the weight by at least 5. If, however, Dominator is unable to find such a sequence of moves mi,..., mk, then we will see that the structure of
CO
the residual forest is determined (see Observation 12 later in the section). This structure enables Dominator to adopt a revised strategy that once again guarantees on average the weight decrease resulting from each played vertex in the game is at least 5.
More precisely, Dominator's strategy proceeds as follows. By Lemma 11, we know the structure of each component of the residual forest.
Suppose the residual forest contains a component Ki,3, with a blue leaf, v say, and three white vertices (see Figure 1(d)). In this case, Dominator plays as his move mi the white central vertex to produce a new component Ki,3 in the residual graph, with three blue leaves and a central green vertex. Let Tv denote this resulting component. The decrease in weight, wi, associated with move mi is 5. If Staller responds by playing her move m2 on a vertex from Tv, then the decrease in weight, w2, associated with her move m2 is 9 and Inequality (1) is satisfied where here k = 2. If, however, Staller plays her move m2 from a different component, then
a
u	13
13
GO CD
■ i-H J-H
CD
u
a
CD U
Dominator plays his move m3 from Tv resulting in w3 = 9. If the game is complete after move m3, then, noting that w2 > 3, Inequality (1) is satisfied where here k = 3 (noting that ^3=1 wi > 5 + 3 + 9 = 17 > 5k). If the game is not complete after move m3, then irrespective of what move m4 Staller plays we have w4 > 3, implying that once again that Inequality (1) is satisfied where here k = 4 (noting that ^4=1 wi > 5 + 3 + 9 + 3 = 20 > 5k). Hence we may assume that the residual forest contains no component K1,3, with a blue leaf and three white vertices, for otherwise Inequality (1) is satisfied.
Suppose there is a component T in the residual forest that contains a subgraph as illustrated in Figure 2(b), where v denotes the blue leaf. Let w and x denote the (white) vertices at distance 1 and 2, respectively, from v in T. Dominator now plays as his move m1 an arbitrary (blue) vertex at distance 3 from v in T. The decrease in weight, w1, associated with move m1 is at least 6. Let Tv be the resulting component that contains v and note that Tv = P3 and Tv contains two blue leaves (namely, v and x) and one central white vertex, namely w. If Staller responds by playing her move m2 on v or x, then w2 = 8 and Inequality (1) is satisfied where here k = 2 (noting that w1 + w2 = 6 + 8 = 14 > 5k). If, however, Staller plays her move m2 from a component different than Tv, then Dominator plays his move m3 from Tv resulting in w3 = 8. If the game is complete after move m3, then Inequality (1) is satisfied where here k = 3 (noting that w2 > 3 and 3=1 wi > 6 + 3 + 8 = 17 > 5k). If the game is not complete after move m3, then irrespective of what move m4 Staller CM plays we have w4 > 3, implying that once again Inequality (1) is satisfied where here k = 4 (noting that ^4=1 wi > 6 + 3 + 8 + 3 = 20). Hence we may assume that the residual forest contains no subgraph as illustrated in Figure 2(b).
Suppose there is a component T in the residual forest that contains a subgraph as illustrated in Figure 2(c) or 2(d), where v denotes the blue leaf. Let w be the CO neighbor of v, and let x and y denote the (white) neighbors of w different from v.
Dominator now plays as his move m1 the vertex w. The decrease in weight associated with move m1 is w1 = 5. Let Tv be the resulting component that contains v. Note that Tv = K1,3, which contains three blue leaves (namely, v, x, and y) and one central green vertex, namely w. If Staller responds by playing her move m2 on a playable vertex in Tv (namely on v, x or y), then w2 = 9 and Inequality (1) is satisfied where here k = 2 (noting that w1 + w2 = 5 + 9 = 14 > 5k). If, however, Staller plays her move m2 from a component different than Tv, then Dominator plays his move m3 from Tv resulting in w3 = 9. As before, Inequality (1) is satisfied with k = 3 (if move m3 completes the game) or k = 4. Hence we may assume that the residual forest contains no subgraph as illustrated in Figure 2(c) or 2(d).
CD
By our earlier assumptions and by our structural lemma, namely Lemma 11, if T is an arbitrary component in the residual forest then T has one of the three possible structures illustrated in Figure 1(b), 1(c) or 1(e) or T has the structure in Lemma 11(c).
c
r
o
CM CM
CO

CM
r
vD A
O
We define next a white component to be a component obtained from the residual forest by deleting all the blue vertices. We note that every white component contains only white vertices. Further every white component is a path on at least two vertices. A white component isomorphic to a path Pn we call a white Pn-component.
Suppose that there is a white component, say C, with at least four vertices. Let v be a leaf in C. Since every white component is path, there is a path Pv on four vertices emanating from v in C. Let this path be given by Pv: vwxy, where either y is a leaf in C or y has degree 2 in C. We note that the neighbors of v, w, and x, if any, in the residual forest that do not belong to the path Pv are all blue vertices. Dominator now plays the vertex x as his move m1 in the residual forest, which results in w1 > 5. Let Tv be the resulting component in the residual forest that contains v. We note that in Tv the colors of the vertices v, w, x, and y are white, blue, green, and blue, respectively. Every neighbor of v in Tv, if any, that is different from w is a blue vertex, while all neighbors of x in Tv are blue vertices.
If Staller responds by playing her move m2 on a neighbor of v or on a neighbor of x in Tv, then w2 > 5 and Inequality (1) is satisfied where here k = 2 (noting that w1 + w2 = 5 + 5 = 10 > 5k). If, however, Staller plays her move m2 on a vertex that is neither a neighbor of v nor a neighbor of x, then Dominator plays as his move m3 the vertex w resulting in w3 > 9. Analogously as before, Inequality (1) is satisfied with k = 3 (if move m3 completes the game) or k = 4. Hence we may assume that every white component contains at most three vertices; that is, every white component is a path P2 or a path P3.
¡5 CO CO
CO
2	Suppose there is a white P3 component given by vwx, where w has a blue neigh-
bor, say y, in the residual forest. The structure of the component of the residual forest that contains this white P3 is described in Lemma 11(c), and hence the vertex y has degree 2 and has two white neighbors. Dominator now plays in the residual forest as his move m1 the vertex y, which gives a decrease in weight of w1 and w1 > 6. Let Tv be the resulting component in the residual forest that contains v. We note that in Tv the vertex w is colored blue and has degree 2 (with neighbors v and x) and both v and x are white vertices all of whose neighbors are blue. If Staller responds by playing her move m2 on a neighbor of v or on a neighbor of x in Tv, then w2 > 6 and Inequality (1) is satisfied where here k = 2 (noting that w1 + w2 > 6 + 6 = 12 > 5k). If, however, Staller plays her move m2 on a vertex that is neither a neighbor of v nor a neighbor of x, then Dominator plays as his move m3 the vertex w resulting in w3 > 10. Analogously as before, Inequality (1) is satisfied with k = 3 (if move m3 completes the game) or k = 4. Hence we may assume that if there is a white P3-component, then the central vertex of this path has degree 2
CD
U
CD
in the residual graph.
U
a
CD U
Suppose that there are two blue vertices of degree 2 that are at distance 3 apart in a component, T, of the residual forest. By Lemma 11(c)(iii), there exists a path

CM
r
vD
lO
a»
viv2... v8 in T where v3 and v6 are colored blue and the remaining vertices on the path are colored white. By our earlier assumptions, v4 is the only white neighbor of v5, and v5 is the only white neighbor of v4. Dominator now plays as his move m1 the vertex v3, and we see that w1 > 6. Let T' be the resulting component in the residual forest that contains v4, and note that v4 is a blue leaf in T' with v5 as its (white) neighbor. If Staller responds by playing her move m2 on a neighbor of v5, then w2 > 6 and Inequality (1) is satisfied where here k = 2 (noting that w1 + w2 > 6 + 6 = 12 > 5k). If, however, Staller plays her move m2 on a vertex that is not a neighbor of v5 in T', then Dominator plays as his move m3 the vertex v6. This gives w3 > 8. Analogously as before, Inequality (1) is satisfied with k = 3 (if move m3 completes the game) or k = 4. Hence we may assume that no two blue vertices of degree 2 in a component of the residual forest are at distance 3 apart. The 1 structure of the residual forest is now determined and is described in the following observation.
o
Observation 12 At this stage in the game, if T is an arbitrary component in the residual forest F, then one of the following holds.
(I)	T = P3, with a blue leaf and two white vertices.
(II)	T = P3, with three white vertices.
(III)	T = P4, with two blue leaves and two white (central) vertices.
(IV)	T has the structure in Lemma 11(c) with the following additional restrictions:
•	Every white component is a path P2 or a path P3.
•	The central vertex of a white P3-component has degree 2 in F.
•	Exactly one vertex of a white P2-component is a leaf in F.
i
CM 00 CM CM
¡5 CO CO
We refer to the components described in Observation 12 as special components. We remark that every special component that is not of type-I, -II, or -III is a type-IV component and contains at least five vertices. Let k be the number of special components of type-IV in the residual forest F. We note that F may possibly also contain special components of type-I, -II, or -III. We now distinguish the special components of type-IV into two subtypes. A type-IV component, T, with the property that all its white components (that is, the components resulting from removing the blue vertices from T) are P2-components we call a type-IV(a) component. A type-IV component, T, with the property that T contains at least one white P3-component we call a type-IV(b) component. Let k1 and k2 denote the number of type-IV(a) and type-IV(b) components, respectively, in F. Hence k = k1 + k2.
Let p2 and p3 denote the number of (white) P2-components and P3-components, respectively, that result from removing all blue vertices from type-IV components. Thus the number of white vertices that belong to type-IV components is 2p2 + 3p3. Let b denote the number of blue vertices that belong to type-IV components. We construct a bipartite graph, B, where the vertices in one partite set are the blue
U
a
CD U

CSF
r
vD
vertices that belong to type-IV components and the vertices in the other partite set correspond to the white components of type-IV components. Each edge of B joins a blue vertex and a white component to which the blue vertex belongs. It follows that B is a forest of order b + p2 + p3, size 2b (since every blue vertex is adjacent to exactly two white vertices from different white components) having k components. Hence, b + p2 + p3 = 2b + k, or, equivalently, b = p2 + p3 — k.
iH
When a component, T, of the residual forest has been identified as a type-IV component and some of its vertices are later played, we will continue to refer to (the residual part of) T as a type-IV component even though it no longer has the structure required to be type-IV component. If no vertex in a type-IV component has yet been played at a particular point in the game, we call such a component a free -component. We note that a blue vertex in a free-component has degree 2 with two white neighbors.
Dominator's strategy is as follows. His aim is to play on a vertex with two white neighbors whenever such a vertex exists. If no such vertex exists, then he plays a vertex that decreases the weight by as much as possible. More precisely, Dominator makes his next move according to the following options.
• Option 1. Dominator selects a free type-IV(a) component, if such a compo-
CM
nent exists, and plays an arbitrary blue vertex.
CM	• Option 2. If option 1 is not possible, then Dominator selects a free type-IV(b)
00 CM CM
CD
■ i-H J-H
CD
component, if such a component exists, and plays an arbitrary white vertex with two white neighbors.
•	Option 3. If neither Option 1 nor Option 2 is possible, then Dominator selects a vertex with two white neighbors in some type-IV component, if such a vertex exists.
I-H
•	Option 4. If none of Options 1, 2 or 3 is possible, then every playable vertex in a type-IV component totally dominates exactly one new white vertex, and Dominator plays a vertex (not necessarily in a type-IV component) that decreases the weight by as much as possible.
If Staller at any point plays a vertex in a component that is not a free component, then Dominator makes his next move according to the Options 1, 2, 3, and 4.
Suppose Staller plays a vertex in a free-component, T. If T is a type-IV(a) component, then Dominator responds by playing his next move according to Options 1, 2, 3, and 4 above. Suppose, however, that T is a type-IV(b) component. We note that T contains a white path P3, say uvw, where all three vertices are colored white, v has degree 2 in T, and the neighbors of u (respectively, w) not on this path, if any, are blue vertices. Further at least one of u and w has a blue neighbor in T.

CM
r
vD
We proceed further with the following claim.
On the one hand, if Staller plays on v or plays on a blue vertex, then two new white vertices are totally dominated. In this case Dominator responds by playing his next move according to Options 1, 2, 3, and 4. On the other hand, if Staller plays on a vertex in T that is neither a blue vertex nor the vertex v, then Dominator responds by playing as his next move the vertex v.
This strategy of Dominator guarantees that at least [ki/2] + max{k2,p3/2} moves totally dominate two new white vertices from type-IV components when played. Let M1 be the total number of moves played from the k type-IV components of F. Since there are 2p2 + 3p3 white vertices from type-IV components, we have that
Mi < 2p2 + 3p3 - k1 - max {k2, .
2 2
Let be the sum of the weights of all vertices that belong to type-IV components of F. Recalling that k = k1 + k2 and b = p2 + p3 — k, we have that
0
6 = 4 x (2p2 + 3p3)+2 x b = 8p2 + 12P3 + 2(P2 + P3 — k) = 10p2 + 14p3 — 2ki — 2k2.
1
Claim A £i > 5Mi.
CO CM
Proof of Claim A. We consider two possibilities.
Case 1. k2 > p3/2. In this case, we note that ki + 6k2 > ki + 3p3 > 2p3. Therefore, the following sequence of equivalent inequalities holds.
CO
i (14p3 — 22ki — 2k2) > 3p3 — 2 ki — k2
^ (i — 54 ki + (1 — 14 k2 > 5P3 ^ ki + 6k2 > 2p3.
Further in this case when k2 > p3/2, we see that Mi < 2p2 + 3p3 — ki/2 — k2 and
{i = 5 x (2p2 + 1 (14p3 — 2ki — 2k2)) > 5 x (2p2 + 3p3 — ki/2 — k2) > 5Mi.
5
CO CD
Case 2. k2 < p3/2. In this case, we note that 3p3 + ki > 6k2 + ki > 4k2. Therefore, the following sequence of equivalent inequalities holds.
5 (14p3 — 2ki — 2k2) > 3p3 — 2 ki — |p3
^	i0 P3 + i0 ki	> 2 k2
^	3p3 + ki	> 4k2.
a
K	18
Further in this case when k2 < p3/2, we see that M1 < 2p2 + 3p3 — ki/2 — p3/2
CSF
lO
o
CSF
1
CSF 00 CSF CSF
CO CO
and
, 1
£1 = 5 x (2p2 + 7(14p3 - 2ki - 2k2)) > 5 x (2p2 + 3pa - ki/2 - pa/2) > 5Mi. 5
In both cases, £1 > 5M1. This completes the proof of Claim A.	□
Jh
Let M2 be the total number of moves played in type-I, type-II, and type-III special components of F and let £2 be the sum of the weights of all vertices that belong to type-I, type-II, or type-III special components of F. We proceed further with the following claim.
Claim B {2 > 5M2.
Proof of Claim B. Let s1, s2, and s3 denote the number of type-I, type-II, and typeIII special components. The total number of vertices in such special components is given by 3s1 + 3s2 + 4s3. Each of these three special components needs two moves to complete the game on that component (irrespective of whether Dominator or Staller plays first on it). Hence M2 = 2(s1 + s2 + s3). Each type-I, type-II, and type-III special component contributes a weight of 10, 12, and 12, respectively, to the weight of F. We conclude that {2 = 10si + 12s2 + 12s3 > 5 x 2(si + S2 + S3) = 5M2. □
The total number of moves played to complete the game is M1+M2. Further, the total decrease in weight is £1 + £2, and Claims A and B imply £1 + £2 > 5(M1 + M2). Consequently, on average the weight decrease resulting from the M1 + M2 moves is at least 5, as desired.
The strategy of Dominator implemented in this section shows that on average the weight decrease resulting from each played vertex in the game is at least 5. We state this formally as follows.
Theorem 13 In a residual forest F, we have that Ytg(F) < w(F)/5 .
6 Proof of Theorem 1 and a General Bound
m
In this section we present a proof of our main result, namely Theorem 1. Recall its statement.
CD
Theorem 1 Let F be a forest on n vertices in which every component contains at least three vertices. Then,
•C	Ytg(F) < 4n and 7tg(F) < ^.
a
V	19
o
Proof. Coloring the vertices of F with the color white we produce a colored-forest in which every vertex is colored white and every component contains at least three vertices. In particular, we note that F has n white vertices and has weight w(F) = 4n. Applying Theorem 13 to the resulting colored-forest F, we have that Ytg(F) < 4n/5. To prove the upper bound on the Staller-start game total domination number, we note that the first move of Staller is on a white vertex with at least one white neighbor and decreases the weight by at least 3. If RF denotes the resulting residual colored-forest, then w(RF) < w(F) — 3 and Ytg(F) = 1 + Ytg(RF). Applying Theorem 13 to the residual forest RF, we have that
2	7tg(F) = 1 + Ytg(RF) < 1 + ^ < 1 + ^ = ^^.
This completes the proof of Theorem 1.	□
o
When either Game 1 or Game 2 is played on a P2 exactly two moves are required. Using the bounds in Theorem 1 we are now able to prove general upper bounds for the total domination games played on any forest that has no isolated vertices.
Corollary 14 If F is a forest of order n with k components of order 2 and no isolated vertices, then
4n + 2k	4n + 2k + 2
Ytg (F) <-— and Ytg (F) <
5 5
Proof. If every component of F has order at least 3, then the bounds are the same as in Theorem 1. If all the components of F have order 2, then every vertex of F will be played in both Game 1 and Game 2, and the upper bounds follow immediately. Finally, suppose F has at least one component of order 2 and at least one component of larger order. Let Fi denote the union of all the components of F that have order at least 3, and let F2 be the union of all k components of order 2. Note that F2 has order 2k, and F1 has order n — 2k. The forest F is the disjoint union of these two subforests.
When Game 1 is played on F, Dominator's strategy is to make an optimal move in Game 1 played on F1. If on any turn Staller plays a vertex v in F2, then Dominator plays the neighbor of v. Otherwise, Dominator always responds to Staller's move with an optimal move in the subforest F1. Following this strategy it follows from Theorem 1 that
4(n — 2k) , 4n + 2k
Ytg (F) < Ytg (Fi) + 2k < -^ + 2k =---.
5 5
When Game 2 is played on F the strategy of Dominator is similar to that in Game 1. In particular, when Staller plays a vertex in F1, Dominator responds with an
optimal move in Game 1 restricted to Fi. When Staller plays a vertex v in F2,
Ytg(F) < Yg(Fi) + 2k < 4(n 2k) ' 2 + 2k = 5
in
o
CM
I
S
CO
Dominator plays the neighbor of v. In this way Dominator can limit the number of moves in Fi to Ytg(Fi). Since all 2k vertices of F2 must be played, Theorem 1 implies
4(n - 2k) + 2	4n + 2k + 2
□
We believe that the upper bounds of Theorem 1 cannot be achieved and pose the following conjecture, which we call the |-Game Total Domination Conjecture or, simply, the |-Conjecture. i-H 3
4-Conjecture: Let F be a forest on n vertices in which every component contains at least three vertices. Then,
^	Ytg (F) < 3n and ^ (F) < ^.
We remark that if the |-Conjecture is true, then the upper bound on the Dominator-start game total domination number is tight as may be seen by taking, for example, F = kiP4 U k2P8 where ki,k2 > 0 and ki + k2 > 1. Since Ytg(P4) = Ytg(P4) = 3 and Ytg(P8) = Ytg (Ps) = 6, the optimal strategy of Staller is whenever Dominator starts playing on a component of F, she plays on that component and adopts her optimal strategy on the component. This shows that Ytg(F) = 3k1 + 6k2 = 3n/4, where n = 4k1 + 8k2 is the number of vertices in F. That the upper bound on the Staller-start game total domination number given the
4
4-Game Total Domination Conjecture is tight may be seen by taking, for example,
F = P5 (noting that here yL(F) = 4 = (3n + 1)/4 and n = 5).
Acknowledgements
Research supported in part by the South African National Research Foundation and the University of Johannesburg, by the Ministry of Science of Slovenia under the grants P1-0297, and by a grant from the Simons Foundation (#209654 to Douglas Rall) and by the Wylie Enrichment Fund of Furman University.
References
[1] B. Bresar, P. Dorbec, S. Klavzar, and G. Kosmrlj, Domination game: effect of edge- and vertex-removal, manuscript (2013).
a
u	21
21
[2] B. Bresar, S. KlavZar, D. F. Rail, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010), 979-991.
vO	[3] B. BreSar, S. KlavZar, D. F. Rail, Domination game played on trees and span-
ning subgraphs, Discrete Math. 313 (2013), 915-923.
[4] B. Bresar, S. KlavZar, G. Kosmrlj, D. F. Rall, Domination game: extremal families of graphs for the 3/5-conjectures, Discrete Appl. Math. 161 (2013), 1308-1316.
m
o
o» o
CSF
i
CSF 00
u
a
CD U
[5]	Cs. Bujtas, Domination game on trees without leaves at distance four, Proceedings of the 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (A. Frank, A. Recski, G. Wiener, eds.), June 4-7, 2013, Veszprem, Hungary, 73-78.
[6]	P. Dorbec, G. Kosmrlj, and G. Renault, The domination game played on unions
of graphs, manuscript, 2013.
[7]	T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
[8]	M. A. Henning, S. Klavzar, D. F. Rall, Total version of the domination game, manuscript, 2013.
[9]	M. A. Henning, A. Yeo, Total Domination in Graphs. Springer Monographs in
Mathematics, ISBN-13: 978-1461465249 (2013).
[10]	W. B. Kinnersley, D. B. West, R. Zamani, Extremal problems for game domination number, SIAM J. Discrete Math. 27 (2013), 2090-2017.
[11]	W. B. Kinnersley, D. B. West, and R. Zamani, Game domination for grid-like graphs, manuscript, 2012.
[12]	G. Kosmrlj, Realizations of the game domination number, J. Comb. Optim., in press. DOI: 10.1007/s10878-012-9572-x.
[13]	R. Zamani, Hamiltonian cycles through specified edges in bipartite graphs, domination game, and the game of revolutionaries and spies, Ph. D. Thesis, University of Illinois at Urbana-Champaign. Pro-Quest/UMI, Ann Arbor (Publication No. AAT 3496787)
• i