IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 49 (2011), 1162
ISSN 2232-2094
DOMINATION GAME PLAYED ON TREES AND SPANNING SUBGRAPHS
Boštjan Brešar Sandi Klavžar Douglas F. Rail
Ljubljana, September 27, 2011
o
CM IN
cm
u
Domination game played on trees and spanning

CD
CD CO
O» O
u
a
CD U
subgraphs
Boštjan Bresar*
a	Faculty of Natural Sciences and Mathematics
University of Maribor, Slovenia bostjan.bresar@uni-mb.si
Sandi Klavzar*
vD
Faculty of Mathematics and Physics University of Ljubljana, Slovenia and
Faculty of Natural Sciences and Mathematics University of Maribor, Slovenia sandi.klavzar@fmf.uni-lj.si
Douglas F. Rant Herman N. Hipp Professor of Mathematics Department of Mathematics, Furman University Greenville, SC, USA doug.rall@furman.edu
CO
August 29, 2011
CM
Abstract
The domination game, played on a graph G, was introduced in [3]. Vertices are chosen, one at a time, by two players Dominator and Staller. Each chosen vertex must enlarge the set of vertices of G dominated to that point in the game. Both players use an optimal strategy-Dominator plays so as to end the game as quickly as possible, Staller plays in such a way that the game lasts as many steps as possible. The game domination number jg (G) is the number of vertices chosen when Dominator starts the game and the Staller-start game domination number Yg(G) when Staller starts the game.
CD
* Supported by the Ministry of Science of Slovenia under the grants P1-0297 and J1-2043. The author is also with the Institute of Mathematics, Physics and Mechanics, Jadranska 19, 1000 Ljubljana.
J( Research supported by the Hipp Endowed Chair in Mathematics and the Wylie Enrichment Fund of Furman University. Part of the research done during a sabbatical visit at the University of Ljubljana.
in cm
In this paper these two games are studied when played on trees and spanning subgraphs. A lower bound for the game domination number of a tree in terms of the order and maximum degree is proved and shown to be asymptotically tight. It is shown that for every k, there is a tree T with (jg (T), (T)) = (k, k + 1)
CD	and conjectured that there is none with (jg(T),y' (T)) = (k, k — 1). A relation
between the game domination number of a graph and its spanning subgraphs is considered. It is proved that for any integer i > 1, there exists a graph G and its spanning tree T such that Yg(G) — Yg(T) > i. Moreover, there exist 3-connected graphs G having a spanning subgraph such that the game domination number of the spanning subgraph is arbitrarily smaller than that of G.
CD
Keywords: domination game, game domination number, tree, spanning subgraph AMS subject classification (2010): 05C57, 91A43, 05C69
VO i—l
1 Introduction
•
The domination game played on a graph G consists of two players, Dominator and Staller who alternate taking turns choosing a vertex from G such that whenever a vertex is chosen by either player, at least one additional vertex is dominated. 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 Yg (G) is the number of vertices chosen when Dominator starts the game provided that both players play optimally. Similarly, the Staller-start game domination number Yg (G) is defined for the game when Staller starts the game. The Dominator-start game and the Staller-start game will be briefly called Game 1 and Game 2, respectively.
This game was introduced in 2010 ([3]) but was brought to the authors' attention back in 2003 by Henning [4]. Among other results, the authors of [3] proved a lower bound for the game domination number of the Cartesian product of graphs and established a connection with Vizing conjecure; for the latter see [2]. The Cartesian product was further investigated in [6] where the behavior of lim^.^ Yg (Km □ Pe)/i was studied in detail.
In the rest of this section we give some notation, definitions, and recall results needed later. Then, In Section 2 we prove a general lower bound for the game domination number of a tree. In Section 3 we consider which pairs of integers (r, s) can be realized as (Yg(T),Y>g(T)), where T is a tree. It is shown that this is the case for all pairs but those of the form (k,k — 1). This increases the previously known pairs that can be realized by connected graphs. For the pairs (k, k — 1) we conjecture that they cannot be realized by trees. In the final section we study relations between the game domination number of a graph and its spanning subgraphs. Among other results we construct graphs G having spanning trees T with Yg (G) — Yg (T) arbitrarily large. This is rather surprising because the domination number of a spanning tree (or a spanning subgraph) can never be smaller than the domination number of its supergraph.
• i
£ CO CO
IN CM
Throughout the paper we will use the convention that di,d2,... denotes the sequence of vertices chosen by Dominator and si,s2,... the sequence chosen by Staller. We say that a pair (r, s) of integers is realizable if there exists a graph G such that Yg(G) = r and Yg(G) = s. Following [6], we make the following definitions. A partially dominated graph is a graph in which some vertices have already been dominated in some turns of the game already played. A vertex u of a partially dominated graph G is saturated if each vertex in N[u] is dominated. The residual graph of G is the graph obtained from G by removing all saturated vertices and all a edges joining dominated vertices. If G is a partially dominated graph then Yg(G) and yg (G) denote the optimal number of moves remaining in Game 1 and Game 2, respectively.
Contrary to the game chromatic number (see [1] for a survey on this related graph invariant), the game domination number of a graph G can be bounded in terms of the domination number y(G) of G:
CD
CD CO
r
CM vO
Theorem 1.1 ([3]) For any graph G, y(G) < Yg (G) < 2y(G) - 1.
o
It was demonstrated in [3] that in general Theorem 1.1 cannot be improved. More precisely, for any integer k > 1 and any 0 < r < k — 1, there exists a graph G with y(G) = k and Yg (G) = k + r.
The game domination number and the Staller-start game domination number are always close together as the next result asserts.
U
CD CO
u
a
CD U
Theorem 1.2 ([3, 6]) For any graph G, \y9(G) — Yg(G)| < 1.
00
By Theorem 1.2 only pairs of the form (r, r), (r, r+1), and (r, r—1) are realizable.
The following lemma, due to Kinnersley, West, and Zamani [6] in particular implies Yg (G) < Yg(G) + 1, which is one half of Theorem 1.2. The other half was earlier proved in [3].
CO
CO Lemma 1.3 (Continuation Principle) Let G be a graph and A, B C V(G). Let Ga and GB be partially dominated graphs in which the sets A and B have already been dominated, respectively. If B C A, then Yg (Ga) < Yg (Gb) and Yg (Ga) < Yg (Gb).
We wish to point out that Continuation Principle is a very useful tool for proving results about game domination number. In particular, suppose that at some stage of the game a vertex x is an optimal move for Dominator. Then, if there exists a vertex y such that the undominated part of N[x] is contained in N[y], then y is also an optimal selection for Dominator and we can thus assume (if necessary) that he
plays y.
2 A lower bound for trees
IN
In this section we give a lower bound on the game domination number of trees and show that it is asymptotically sharp. Before we can state the main result, we need the following:
Lemma 2.1 Let F be a partially dominated tree and suppose it is Staller's turn. Then Staller can make a move that dominates at most two new vertices.
Proof. Let A be the set of saturated vertices of F and let B be the set of vertices of F that are dominated but not saturated. Let C = V(F) — (A U B). Let F' be the subforest of F induced by B U C but with edges induced by B removed (that is, F' is the residual graph). We may assume that C = 0 since the game is not over yet.
vO
Then F' has a leaf x. If Staller plays x, she dominates at most two vertices in C. If x € B, Staller dominates exactly one vertex in C.	□
o Ö
Note that the move guaranteed by Lemma 2.1 may not be an optimal move for Staller. For instance, the optimal first move of Staller when playing on P5 is the middle vertex of P5, thus dominating three new vertices. Also, we will see later that an optimal first move for Staller when playing Game 2 on the tree Tr from Figure 2 is s1 = w thus dominating r + 1 new vertices.
o
Theorem 2.2 Let T be a tree on vertices v1, v2,..., vn, where deg(vi) > deg(v2) > ■ ■ ■ > deg(vn). For j > 1, let Xj = ^jj=1 deg(v^) + 3j. Let r be the smallest integer such that xr > n. Then Yg (T) > 2r — 1 when xr — 2 > n, and Yg (T) > 2r when Xr > n. In particular,
2n
00
Yg (T) >
A(T) + 3
1
£
Proof. By Lemma 2.1, Staller can move in such a way that at most two new vertices are dominated on each of her moves. Let us suppose that Dominator plays optimally when Staller plays to dominate at most two new vertices on each move. Let d1, s1, d2, s2,..., dt, st be the resulting game, where we assume that st is the empty move if T is dominated after the move dt. Let f (dj) (resp. f (si)) denote the number of newly dominated vertices when Dominator plays di (resp. when Staller plays si). Suppose the game ends on Staller's move. Then
HH
t t t n = y (f (di) + f (sj)) < y ((deg(vj) + 1) + 2) = ^ deg(Vj) + 3t = xt.
i= 1 i= 1 i= 1
By the choice of r we find that t > r. Since this strategy may not be an optimal one for Staller, it follows that Yg (T) > 2t > 2r. Similar arguments gives Yg (T) > 2r — 1 if the game ends on Dominator's move.
Ö
IN CM
$H
CD
a
CD
a
CD CO
CM vO
0 Ö
o
CM
1
CM CO CM CM
£ CO CO
If Staller ends the game, then n < r(A(T) + 3) < 2Yg(T)(A(T) + 3) and hence
Yg (T) >
2n
since 7g(T) is integral. If the game ends on Dominator's move,
A (T )+3
then (T) > 2r — 1 and hence
n < r(A(T) +3) < Yg(T) + 1(A(T) + 3).
This is equivalent to 2n < (Yg(T) + 1)(A(T) + 3) which in turn implies that
2n
Yg (T) >
A(T) + 3
- 1
	" 2n "
	A(T) + 3
- 1
and we are done.
□
To see that Theorem 2.2 is asymptotically optimal, consider the caterpillars T(s,t) shown in Figure 1.
s — 1 s — 1 s — 1
s - 1 s - 1
Figure 1: Caterpillar T(s,t)
Clearly, T(s,t) has n = st vertices. Let s > t + 1, then it is easy to see that Yg(T(s,t)) = 2t — 1. Indeed, since s — 1 > t, Staller can select a leaf after each of the first t — 1 moves of Dominator. Hence after Dominator selects the t vertices of high degree, the game is over. By Theorem 2.2, Yg(T(s,t)) > S+4 — 1, which for a
fixed t, tends to A(T(S"))+3 — 1 = 24 — 1 ~ 2t — 1 as s ^
CO CD
Jh
CD CO
a
CD Jh
3 Pairs realizable by trees
In this section we are interested which of the possible realizable pairs (r, r), (r, r +1), and (r, r — 1) can be realized on trees. It was observed in [3] that all pairs (k,k), k > 1, are realizable by trees. We now show that pairs (k, k + 1) are also realizable by trees. On the other hand, we prove that the pairs (3, 2) and (4,3) cannot be realized by trees and conjecture that no pair (k +1, k), k > 1, is realizable by a tree. (Clearly, no graph realizes the pair (2,1).)
Theorem 3.1 For any k > 1, there exits a tree T such that Yg(T) = k and Yg(T) = k + 1.
IN CSF
Proof. Stars Ki,n, n > 2, confirm the result for k = 1. For k = 2 consider the tree
on five vertices obtained from K1,3 by subdividing one edge. In the rest of the proof
assume that k > 3. We distinguish three cases based on the parity of k mod 3. J-i
Case 1: (3r, 3r + 1).
Let r > 1 and consider the tree Tr of order 5r + 1 from Figure 2.
X1 X2 X ai b1 ci
ft CD
vD
O Ö

£ CO CO
CD
r
w
Figure 2: Tree Tr
We claim that Yg (Tr) = 3r. Dominator can prevent Staller from forcing three moves in some Xj only if Staller does not follow Dominator on Xj but instead plays w. But this move by Staller uses w and eventually three moves will be made on each remaining Xj. (For example, play could be as follows: d1 = a1, s1 = b1, d2 = a2,
s2 = b2, d3 = a3, s3 = w, d4 = c3, s4 = b4,____ This game has 3r moves.) If, on the
other hand, Staller continues to follow Dominator in all of Xj, then w is an illegal move. Hence Yg(Tr) = 3r.
Consider now Game 2. Let Staller play s1 = w and then follow Dominator on Xj as soon as Dominator plays on Xj. In this way, on every Xj, 1 < i < r, three vertices
will be played in the game, hence Yg(Tr) > 3r + 1. By Theorem 1.2, Yg(Tr) = 3r + 1. Case 2: (3r + 1, 3r + 2).
For r > 1 let T/ be the graph of order 5r + 3 obtained from Tr (the tree from Figure 2) by attaching a path of length 2 to w with new vertices y and z, where z is a pendant vertex (and y adjacent to w and z). Suppose Dominator plays a1 in Game 1. If Staller now plays s1 = w and Dominator plays d2 = c1, then Staller guarantees 3 from each of X2, X3,..., Xr. Thus if Staller plays s1 = w, then 3r + 1 moves will be made. On the other hand, Staller could play s1 = b1 which forces three vertices to be played on X1. Dominator would respond with d2 = a2. Continuing in this manner (with Staller responding with s = bj to d = aj) until two moves have been made on each of X1, X2,..., Xr, then Dominator would play dr+1 = y. In this way, 3r + 1 moves are made.
If Staller follows Dominator on X1, X2,..., Xj, but when dj+1 = aj+1 Staller suddenly plays sj+1 = w, then Dominator plays dj+2 = cj+1. This uses 3i + 2 + 2 +
3(r — (i + 1)) = 3r + 1 moves. Hence Yg(T^) = 3r + 1.
We play Game 2 next. Let s1 = w. Then each Xj will have three played vertices since Staller follows Dominator on each Xj and hence Yg(T) > 3r + 2. By
o
CM IN
a
CD
a» o
CM
i
CO CD
Theorem 1.2, V (T) = 3r + 2
Case 3: (3r + 2, 3r + 3).
In this case consider the tree T" (r > 1) obtained from the tree Tr (of Figure 2) by attaching a path of length 2 to b1, say P = b\,p,q, and a path of length 2 to br, say Q = br ,u,v. Note that if r = 1, then P and Q are attached at the same vertex
bi = br.
Proof that Yg (G) = 3r + 2 is similar to the proof of Case 1 in that Dominator either forces Staller to follow in each Xi or saves one move in some Xi in exchange for Staller playing w. Two more moves are required in order to dominate q and v. (Note that the same argument works also for r = 1.) An optimal strategy in Game 2 is again s1 = w, now each Xi will have three played vertices and there will be two more played vertices because of q and v. Hence Yg(T") > 3r + 3 and we conclude that yg(T') = 3r + 3.	□
i—l
For the (k, k — 1) case we pose: Conjecture 3.2 No pair (k, k — 1), k > 3, can be realized by a tree.
In the rest of the section we prove the first two cases of the conjecture:
Theorem 3.3 No tree realizes the pair (3,2) or the pair (4,3).
Proof. Suppose that a tree T realizes (3,2). It is easy to see that yg(T) = 2 implies that T is either a star K1,n for n > 2 or a P4. In both cases Yg(T) < 2, thus (3,2) is not realizable on trees.
Suppose T is a tree that realizes (4,3), and let d1 = x be an optimal first move CM for Dominator. The residual graph T' has at most 3 components, each of which is CM a partially dominated subtree of T. Note that if one of these partially dominated components F has Yg (F) = 1, then F has exactly one undominated vertex.
Suppose first that T' has three partially dominated components T1,T2,T3 with Ti rooted at the dominated vertex vi. If at least one of these subtrees, say T1 has more than one undominated vertices, then Staller can force at least two moves in T1. Because the other two subtrees each require at least one move, it follows that Yg(T) > 5, a contradiction. Hence, each of T1,T2,T3 has exactly one undominated vertex, and T is the tree of order 7 formed by identifying a leaf from three copies of P3. However, this tree has Staller-start game domination number 4, again contradicting our initial assumption.
Now suppose that T' is the disjoint union of T1 and T2. Note that in this case x cannot be a support vertex in the original tree T. Indeed, if x is adjacent to a leaf y, then when Game 2 is played on T Staller can play first at y which is easily shown to force at least four moves. Thus, deg(x) = 2. If Yg(T1) = 1 = Yg(T2), then T = P5 and Yg(T) = 3, a contradiction.
Note that the Staller-start game domination number of any of these two partially dominated trees cannot exceed 2. We may thus assume without loss of generality
• i
IN CM
$H
CD
a
CD
a
CD CO
CM vO
0 Ö
o
CM
1
CM CO CM CM
£ CO CO
that 2 = Yg(Ti) > Yg(T2). Suppose that Yg(T2) = 2. Staller can then play at vertex x when Game 2 is played on T. After Dominator's first move at least one of Ti or T2 is part of the residual graph, and Staller can then force at least two more moves again contradicting the assumption that (T) = 3. Therefore, T2 is the path of order 2 with one of its vertices dominated.
If Ti is a star with vi as its center or as one of its leaves, then 7(T) = 2 and hence 4 = Yg(T) < 2 ■ 2 — 1, an obvious contradiction. Therefore, Yg(Ti) = 2, but Ti is not a star. A short analysis shows that Ti must be one of the partially dominated trees in Figure 3. Each of these candidates for Ti together with T2 = P2 yields a tree T with either Yg (T) = 4 or Y'g (T) = 3, again contradicting our assumption about T. This implies that the residual graph T' has exactly one component.
vi
vi
vi
wi
t > 1
Wt
wi	wt
i t 1 t
Figure 3: Possible partially dominated trees
By Continuation Principle (Lemma 1.3) it must be the case that x is a support vertex in T because we assumed that x was an optimal move by Dominator. Let A = {vi} and B = 0. Since 7g(Ti) = 3 we apply Lemma 1.3 to get
3 = Yg (T) = Yg (Tb) > Yg (Ta) > 1 + Yg (Ti) = 4.
This establishes the theorem.
□
CO CD
Jh
CD CO
u
a
CD U
4 Game on spanning subgraphs
We now turn our attention to relations between the game domination number of a graph and its spanning subgraphs, in particular spanning trees.
Note that since any graph is a spanning subgraph of the complete graph of the same order, the ratio Yg (H)/Yg (G) where H is a spanning subgraph of G can be arbitrarily large. On the other hand the following result shows that this ratio is bounded below by one half.
o
CM IN
cm
$H
CD
a
CD
a
CD CO
CM vO
0
o
cm
1
cm CO cm cm
£ CO CO
w
CD
$H
CD W
U
a
CD U
Proposition 4.1 Let G be a graph and let H be a spanning subgraph of G. Then
Yg (G) + 1
Yg (H) >
2
In particular, if T is a spanning tree of connected G, then Yg (T) > (Yg (G) + 1)/2.
Proof. Clearly, y(H) > y(G). By Theorem 1.1, Yg(H) > Y(H) and Yg(G) < 2y(G) - 1. Then Yg(H) > Y(H) > y(G) > (Yg(G) + 1)/2.	□
To see that a spanning subgraph can indeed have game domination number much smaller that its supergraph, consider the graph Gt consisting of t blocks isomorphic to the house graph and its spanning subgraph Ht, see Figure 4. Let x be the vertex where the houses of Gt are amalgamated. Note that Dominator needs at least two moves to dominate each of the blocks of Gt. Hence his strategy is to play d\ = x and then finish dominating one block at each move. On the other hand, if not all blocks are already dominated, Staller can play the vertex of degree 2 adjacent to x of such a block B in order to force one more move on B. So in half of the blocks two vertices will be played (not counting the move on x) which in turn implies that Yg (Gt) is about 3t/2. On the other hand, playing Game 1 on Ht, the optimal first move for Dominator is d\ = x. After that Staller and Dominator will in turn dominate each of the triangles, hence Yg(Ht) = t + 1.
Figure 4: Graph Gt and its spanning subgraph Ht
The example of Figure 4 might indicate that spanning subgraphs can have smaller game domination number than their supergraphs provided none is 2-connected. However:
Theorem 4.2 For any m > 3 there exists a 3-connected graph Gm and its 2-connected spanning subgraph Hm such that Yg (Gm) > 2m — 2 and Yg (Hm) = m.
Proof. We form a graph Gm of order n = m(m + 2) as follows. Let X = {&i,i, «¿,2,..., Ui,m} U (xj, yi} for each 1 < i < m, and then set
m
V (Gm) = U Xi .
i= 1
x
x
IN CM
$H
CD
a
CD
a
CD CO
CM vO
The edges are the following. We let (xi, yi, x2, y2,..., xm, ym} induce a complete graph of order 2m. For each p, 1 < p < m we let Xj, induce a complete graph of order m + 2. In addition, for each 1 < i < m — 1 and each i < j < m — 1 we add the edge a^jaj-+i,j. See Figure 5 for G4.
Kfi
a1,4 O
ai,3
ai,2
ai,i o-
Kfi
Kfi
Kfi
0 o
CM
1
CM CO CM CM
£ CO CO
CD
$H
CD C0
Jh
a
CD U
xi	yi X2	y2 X3	y3 X4	y4
Kg
Figure 5: Graph G4
Suppose first that di = xi. Then Staller plays in Xi, say si = ai,i. Then, in each of the next rounds, Continuation Principle implies that Dominator must play in some Xj that has not been played in before and on a vertex of Xj that has a neighbor outside Xj. It will always be possible for Staller to follow Dominator and also play in Xj in each of her first m — 2 moves. Hence by this time, 2m — 4 moves were made. At this stage, there are two undominated vertices in different Xj's with no common neighbor. Hence two more moves are needed to end the game which thus ends in no less than 2m — 2 moves.
Assume next that di = ai,i. Then Staller plays si = xi and we are in the first case. Note that playing di = xi or di = ai,i covers all the cases due to symmetry. Hence Yg (Gm) > 2m — 2.
The spanning subgraph Hm of Gm is obtained by removing all the edges aj,jaj+i,j. By Continuation Principle we may without loss of generality assume that di = xi when Game 1 is played on Hm. But then on each successive move of either of the players the newly dominated vertices are a subset of the Xj on which they play. Hence Yg(Hm) = m.	□
If Yg(G) attains one of the two possible extremal values, y(G) or 2y(G) — 1, we can say more.
Proposition 4.3 Let G be a graph with Yg(G) = y(G) and let H be a spanning subgraph of G. Then Yg (H) > Yg (G).
IN CM
$H
CD
a
CD
a
CD CO
CM vO
0 Ö
o
CM
1
CM CO CM CM
£ CO CO
Proof. 7fl (H ) > y (H) > y (G) = Yg (G).
□
In particular, every spanning tree T of a connected graph G with y g (G) = y (G) has Yg(T) > Yg(G).
Proposition 4.4 Let G be a graph with Yg(G) = 2y(G) — 1 and let H be a spanning subgraph of G with y (H ) = y(G). Then Yg (H ) < Yg (G).
Proof. Yg (H) < 2y(H) — 1 = 2y(G) — 1 = Yg(G).
□
Since every graph G has a spanning forest F such that y(G) = y(F), see [5, Exercise 10.14], we infer:
Corollary 4.5 Let G be a graph with Yg(G) = 2y(G) — 1. Then G contains a spanning forest F (spanning tree if G is connected) such that Yg (F) < Yg (G).
In the rest of this section we focus on spanning trees. First we show that a graph can have the property that all of its spanning trees have game domination number much larger than that of the supergraph. Let n > 3, m = 2r, and let S be the star with center x and leaves v1, v2,..., vm. Let Gm be the graph (of order nm + 1) constructed by identifying a vertex of a complete graph of order n with vj, for each i, 1 < i < m; see Figure 6.
CO CD
5H
CD CO
5H
a
CD U
Figure 6: Graph Gm
We first note that Yg(Gm) = m +1. Let T be any spanning tree of Gm. T has at least one leaf ^ in the subtree Tj of T rooted at Vj when the edge xvj is removed from T (choose ^ = Vj). When Game 1 is played on T, Staller can choose at least half of these leaves	... or let Dominator choose them. Thus in at least half
of T1, T2,..., Tm, two vertices will be chosen. Therefore Yg(T) > m + m/2 = 3m/2, hence we conclude that
3
Yg(T) — Yg (Gm) > ^m — m — 1 = r — 1.
x
o
CM IN
cm
$H
CD
a
CD
Oh CD CO
CM vO
0 £
o
cm
1
cm CO cm cm
£ CO CO
Next we give an example of a spanning tree with game domination number smaller than the one of its supergraph. Consider the graph G and its spanning tree T from Figure 7.
1
o-
Figure 7: Graph G and its spanning tree T
For each of the following pairs of vertices (x, y) from G, if Dominator plays x then Staller can play y and then the game domination number of the resulting residual graph G' will be 2: (1, 6); (2, 3); (3, 2); (4, 8); (8, 4); (7, 3); (6,1); (5,1). Therefore, Yg (G) > 4. Consider now the spanning tree T and let Dominator play 2 on T. For each of the following vertices a, the residual graph T' when Staller plays a is listed in Figure 8. For instance, the left case is when Staller plays a = 5 in which case the residual graph is induced by vertices 6, 7, 8 and the vertex 6 of the residual graph is already dominated as indicated by the filled vertex.
(5,
6 7 8
(6,
7 8
(7,
5 6
(8,
56
Figure 8: Staller's possible moves
In each case we find that the residual graph has game domination number 1 and therefore,
Yg (T) < 3 < Yg (G) .
This rather surprising fact demonstrates the intrinsic difficulty and unusual behavior of the game domination number. But even more can be shown:
Theorem 4.6 For any integer £ > 1, there exists a graph G and its spanning tree T such that Yg(G) — Yg (T) > £.
m
CD
$H
CD
m
u
a
CD U
Proof. We introduce the family of graphs Gk and their spanning trees Tk in the following way. Let k be a positive integer, and for each i between 1 and k, x1, x2, x3, x4, x5 are non-adjacent vertices in Tk, and Qi : y\ylyiyfyf is a path isomorphic to P5 in Tk. Finally x and y are two vertices, such that x is adjacent to xl,x2,x3,x4 and x5 for all i e {1,... ,k}, while y is adjacent to y1 for all i e {1,..., k}, and x and y are also adjacent. The resulting graph Tk is a tree on 10k + 2 vertices. We obtain Gk by adding edges between xj and yj for 1 < i < k,
5
6
7
8
5
6
7
8
IN CM
$H
CD
a
CD
a
CD CO
CM vO
1 < j < 5. See Figure 9 for G4, from which T4 is obtained by removing all vertical edges except xy.
x
0 o
CM
1
CM CO CM CM
£ CO CO
CO CD
$H
CD CO
$H
a
CD Jh
Figure 9: Graph G4
To complete the proof it suffices to show that for any integer k > 1,
5
Yg (Gk) > ^k - 1 and Yg (Tk) < 2k + 3 .
Let us first verify the second inequality, concerning trees Tk. To prove it we need to show that Dominator has a strategy by which at most 2k + 3 moves will be played during Game 1. His strategy is as follows. In his first two moves, he ensures that x and y are chosen. He plays x in his first move, and y in his second move, unless already Staller played y (we will consider this case later). Now, s1 = y implies that s1 is in some Qi, without loss of generality let this be Q1. Hence in Dominator's third move, since y1 is dominated for each i, he can dominate all vertices of Q1. One by one, Staller will have to pick a new Qi to play in, which Dominator will entirely dominate in his next move. Altogether, in each Qi (with a possible exception of one Qi, where Staller can force three vertices to be played), there will be only two vertices played, which yields 2k + 3 as the total number of moves in this game. On the other hand, if s1 = y, then d2 = y3 ensures that in Q1 only two vertices will be played. Moreover, Dominator can follow Staller in each of the remaining Qis to force only two moves in each. Hence the game will finish in 2k + 2 moves.
To prove the first inequality we need to show that Staller has a strategy to enforce at least fk — 1 moves played during Game 1 in Gk. Her strategy in each of the first k moves of the game is to play an x4 for which no vertex from Qi U {x1, x2, x3, x5} has been played before her move. This is clearly possible as Dominator made at most [|] of these moves. Using this strategy she ensures that in each of these |_|J Qis at least two more moves will be needed (since at least y2,y3 and yf are left undominated). The remaining |] paths Qi require two moves each. Hence altogether, there will
be at least 2k + |_|J moves played during Game 1, which implies Yg (Gk) > f k — 1. □
y
References
IN
[1]	T. Bartnicki, J. Grytczuk, H. A. Kierstead, X. Zhu, The map-coloring game, Amer. Math. Monthly 114 (2007) 793-803.
[2]	B. BreSar, P. Dorber, W. Goddard, B. L. Hartnell, M. A. Henning, S. KlavZar, D. F. Rall, Vizing's conjecture: a survey and recent results, J. Graph Theory, in press. DOI: 10.1002/jgt.20565.
a [3] B. Bresar, S. KlavZar, D. F. Rall, Domination game and an imagination strat-
CD CO
egy, SIAM J. Discrete Math. 24 (2010) 979-991. [4] M. Henning, personal communication, 2003.
CM
[5]	W. Imrich, S. KlavZar, D. F. Rall, Topics in Graph Theory: Graphs and Their Cartesian Product, A K Peters, Wellesley, MA, 2008.
i—l
[6]	B. Kinnersley, D. B. West, R. Zamani, Extremal problems for game domination number, manuscript, 2011.
CO CD
$H
CD CO
$H
14
CD
$H