Further Progress on the Heredity of the Game Domination Number

Abstract

The domination game is a two-player game played on a finite, undirected graph G. During the game, the players alternately choose a vertex of G such that each chosen vertex dominates at least one previously undominated vertex. One player, called Dominator, tries to finish the game within few moves, while the second player, Staller, tries to make it last for as long as possible. The game domination number ${\gamma _g}(G)$ is the total number of moves in the game when Dominator starts and both players play optimally. The Staller start game domination number ${\gamma _g'}(G)$ is defined similarly when Staller starts the game. The behaviour of the game domination number on the removal of a vertex and an edge so as that no heredity is possible, in contrast with what is happening for domination. In this paper we consider the special case of no-minus-graphs.

1 Introduction

The game domination number was introduced by Brešar et al. [4]. This parameter is to domination what the game chromatic number is to graph colourings (see e.g. [1]).

Recall that a vertex is said to dominate itself and its neighbours. In the domination game, two players, named Dominator and Staller, alternate turns choosing a vertex in a finite, undirected graph G, and adding it to a set of vertices S. Whenever a player chooses a vertex to add to S, the vertex must dominate at least one vertex not yet dominated by the vertices of S. The game ends when no move is possible, that is when S is a dominating set of the graph. The total number of chosen vertices is called the score of the game. The two players have opposite goals, Dominator tries to minimize the final score while Staller tries to maximize it.

Two graph parameters relative to this game were introduced in [4]. Assuming both players play optimally, the game domination number ${\gamma _g}(G)$ is the score of the game on G when Dominator starts (we say in Game 1), and the Staller start game domination number ${\gamma _g'}(G)$ is the score when Staller starts (in Game 2). Both parameters are studied in parallel since many results hold for both of them. We thus may refer to them on the game domination numbers.

The first and the most natural question is to try to find bounds for the game domination number of a graph. In terms of the order n of the graph, Kinnersley et al. [8] conjectured that ${\gamma _g}(G)$ is bounded above by $\frac{3n}{5}$. Early results on this question for trees can be found in [3, 6].

A natural technique to find bounds for the game domination number would be to find some heredity property: find a graph operation that involves a monotonous behaviour of the game domination number of the graphs. A first natural way of finding heredity is to consider the game within its course, and to have some vertices partially dominated. Given a subset S of vertices in a graph G, we denote by G|S the graph where the vertices of S are considered already dominated. Kinnersley et al. [8] observed that whatever the set S of already dominated vertices, the game last no longer on G|S than on G. More generally,

Theorem 1

(Continuation principle [8]). Let G be a graph and $A, B \subseteq V(G)$. If $B \subseteq A$ then $\gamma _{g}(G|A)\le \gamma _{g}(G|B)$ and $\gamma ^{'}_{g}(G|A) \le \gamma ^{'}_{g}(G|B)$.

This result together with earlier observations [4] on the problem allowed to deduce that the Staller start and the Dominator start game domination number may differ by at most one:

Theorem 2

[4, 8] For any graph G and subset S of vertices, $|{\gamma _g}(G|S)-{\gamma _g'}(G|S)|\le 1$

Another early consideration of heredity for the game domination numbers was made in [5], where the authors proved that the ratio of the game domination number of a graph and of a spanning subgraph could not be bounded. Then, the consequences of vertex and edge removal in a graph were considered in [2] and it is proved that in both cases, the game domination number can either increase or decrease.

Another main track of research on this topic is to compare the behaviour of the Staller start and Dominator start game domination numbers. As mentioned earlier, it is known that the difference is at most one, and that it can occur in both directions. Naturally, it comes that Staller can have the game last longer when she start the game, e.g. on a star; but it may also happen that she makes the game finish earlier when starting, as e.g. on the 5-cycle. This second behaviour is more surprising, and seems to happen on fewer graphs. It may not happen for example on trees. In [7], a special family of graphs was introduced, called no-minus: a graph G is no-minus if for any subset of vertices $S\subseteq V$, ${\gamma _g}(G|S)\le {\gamma _g'}(G|S)$. In that cases, it is never interesting for Staller to pass a move. It is known already that forests [8], tri-split and dually chordal graphs [7] are no-minus graphs. In the following, we consider the case of no-minus graphs for earlier studied parameters, such as edge and vertex deletion.

2 Edge and Vertex Removal in No-Minus Graphs

2.1 Edge Removal

Here, we prove that removing an edge from a no-minus graph can either increase or decrease its game domination number by at most 1.

Theorem 3

If G is a no-minus graph and $e \in E(G)$, then

$\left| \gamma ^{}_g(G) - \gamma ^{}_g(G-e)\right| \le 1$ and $\left| \gamma ^{'}_g(G)-\gamma ^{'}_g(G-e)\right| \le 1$.

Proof

First we prove that $\gamma _g(G)\le \gamma _g(G-e)+1$. It is enough to show that Dominator has a strategy on G such that at most $\gamma _g(G-e)+1$ moves will be played. Both the players play a dominator start game on G, at the same time Dominator imagines a dominator start game played on $G-e$ with at most $\gamma _g(G-e)$ steps. Dominator’s strategy on G is as follows. He copies every move of Staller in the real game to the imaginary game and responds optimally in $G-e$. Each response in the imagined game is then copied back to the real game in G. Let $e=uv$ and if every move of Dominator and Staller are legal, then the real game ends by at most $\gamma _g(G-e)$ steps. Suppose at the $k^{th}$ step Dominator chooses a vertex in the imagined game that is not a legal move in the real game. This is possible only if Dominator chooses a vertex that dominates either u or v itself and all other neighbours of that vertex are already dominated. Suppose that it dominates v only which is already dominated in G. After this move, the set of vertices dominated in both the graphs are same. At this stage the number of moves in the real game is $k-1$ and the next turn is that of Dominator. Therefore $\gamma _g(G) \le k-1+ \gamma _g(G|D)$ where D denotes the set of vertices already dominated in G. But in the imagined game, the next turn is that of Staller and the number of moves at this stage is k. Since Staller did not play optimally in $G-e$, $k+ \gamma ^{'}_g(G-e|D) \le \gamma _g(G-e)$. So,

$$\begin{aligned} \gamma _g(G)&\le k-1+ \gamma _g(G|D)\\&= k-1 + \gamma _g(G-e|D)\\&\le k + \gamma _g(G-e|D)\\&\le k + \gamma ^{'}_g(G-e|D)\\&\le \gamma _g(G-e). \end{aligned}$$

Hence, in this case the real game ends in at most $\gamma _g(G-e)$ steps.

Suppose, at the $k^{th}$ step Staller chooses a vertex in the real game and this is not a legal move in the imagined game. This is possible only if Staller chooses one of the end vertices of e and the other end vertex is the only vertex which is newly dominated. Let v denote the newly dominated vertex. Let D denote the set of vertices dominated in the real game after the $k^{th}$ move, at this stage the set of vertices dominated in the imagined game is $D-{v}$. In the real game, k vertices are already selected by both the players and the next is Dominator’s turn. Therefore, $\gamma _g(G)\le k + \gamma _g(G|D)$. But in the imagined game both the players selected $k - 1$ vertices and the next turn is that of Staller. Therefore $k - 1 + \gamma ^{'}_g(G-e|D-{v})\le \gamma _g(G-e)$. So,

$$\begin{aligned} \gamma _g(G)&\le k + \gamma _g(G|D)\\&\le k + \gamma _g(G-e|D)\\&\le k + \gamma _g(G-e|D-{v})\\&\le k + \gamma ^{'}_g(G-e|D-{v})\\&= k-1+\gamma ^{'}_g(G-e|D-{v}) +1\\&\le \gamma ^{}_g(G-e) + 1. \end{aligned}$$

Hence $\gamma _g(G) \le \gamma _g(G-e) + 1$.

Now we prove that $\gamma _g(G-e) - 1 \le \gamma _g(G)$. This proof is analogous to the proof of $\gamma _g(G-e)\le \gamma _g(G) + 2$ in [2] but we substitute the condition $\gamma _g(G|D)\le \gamma ^{'}_g(G|D)$ instead of $\gamma _g(G|D)\le 1+\gamma ^{'}_g(G|D)$. In both the cases the proof is independent of who moves the first. Hence this proof works for $\gamma ^{'}_g(G)$ also.

2.2 Vertex Removal

If a vertex from a graph G is removed, its game domination number either increases arbitrary large or decreases by at most two [2]. However, if G is a no-minus graph and v is a pendant vertex, we have the following lemma.

Lemma 1

If G is a no-minus graph and v is a pendant vertex, then

$$\begin{array}{rcccl} \gamma ^{}_g(G)-1 &{}\le &{} \gamma ^{}_g(G-v)&{}\le &{} \gamma ^{}_g(G)\\ \\ {\gamma _g'}(G)-1 &{}\le &{} \gamma ^{'}_g(G-v)&{}\le &{} \gamma ^{'}_g(G). \end{array}$$

Proof

First we prove that $\gamma _g(G-v) \le \gamma _g(G|v)$. For that we need to show that Dominator has a strategy on $G-v$ that at most $\gamma _g(G|v)$ moves will be played. The strategy is as follows. Dominator and Staller play an ordinary Dominator start game played on $G-v$ and at the same time Dominator imagines another game played on G|v. He copies every move of Staller in the real game to the imagined game and respond optimally in the imagined game. He then copies back every optimal response in the imagined game to the real game. Every move of Staller in the real game is a legal move in the imagined game. Dominator never chooses v in the imagined game, so every move of Dominator in the imagined game is a legal move in the real game. Hence, the real game ends by at most $\gamma _g(G|v)$ steps. That is $\gamma _g(G-v) \le \gamma _g(G|v)$. By the continuation principle $\gamma _g(G|v)\le \gamma _g(G)$. Hence $\gamma _g(G-v)\le \gamma _g(G)$.

Now, we prove that $\gamma _g(G)\le \gamma _g(G-v)+1$. It is enough to show that Dominator has a strategy on G such that at most $\gamma _g(G-v)+1$ moves will be played. Dominator imagines a dominator start game played on $G-v$ simultaneously with the game played on G. He is copying every move of Staller in the real game to the imaginary game and respond optimally in it. Every optimal response in the imagined game is then copied back to the real game. If all the moves are legal then $\gamma _g(G)\le \gamma _g(G-v)$. Suppose at the $k^{th}$ step Staller chooses a vertex that is not a legal move in $G-v$. This is possible only if Staller chooses a vertex whose neighbours are already dominated except v. Let D denote the set of vertices dominated in the real game after the $k^{th}$ step. But in the imagined game both the players played $k-1$ moves and the next move is that of Staller. Therefore $k-1+\gamma ^{'}_g(G-v|D-v)\le \gamma _g(G-v)$ and hence

$$\begin{aligned} \gamma _g(G)&\le k+ \gamma _g(G|D)\\&\le k +\gamma _g(G-v|D-v)\\&\le k+ \gamma ^{'}_g(G-v|D-v)\\&\le k-1+\gamma ^{'}_g(G-v|D-v)+1\\&\le \gamma _g(G-v)+1. \end{aligned}$$

Hence, $\gamma _g(G)-1\le \gamma _g(G-v)\le \gamma _g(G)$. The proof is independent of who moves the first. So $\gamma ^{'}_g(G)-1\le \gamma ^{'}_g(G-v)\le \gamma ^{'}_g(G)$ also holds.

3 Examples of No-Minus Graphs Attaining Possible Values

3.1 Edge Removal

Trees are no-minus graphs [8]. So, by Theorem  3, $\left| \gamma ^{}_g(T)-\gamma ^{}_g(T-e)\right| \le 1$ and $\left| \gamma ^{'}_g(T)-\gamma ^{'}_g(T-e)\right| \le 1$, for a tree T. Here, we show that all is possible except for $k = 1,~ 2$.

Case 1. $\gamma _g(T)-\gamma _g(T-e)=1$.

For $k=1$ , 2, there is no tree T with $\gamma _g(T) = k$ and $\gamma _g(T-e) = k-1$.

For $k=3$, let T be the graph obtained from $P_4$ by attaching two vertices at one of the end vertex of $P_4$ and let e denote the middle edge of $P_4$. Clearly $\gamma _g(T)=3$ and $\gamma _g(T-e)=2$.

For $k=4$, let T be the graph obtained from $P_3$ by attaching two vertices at both end vertices of $P_3$ and subdivide one of the added edge. If e is the edge of $P_3$ incident to the vertex attached to the subdivided edge. Clearly $\gamma _g(T) = 4$ and $\gamma _g(T-e)=3$.

For $k\ge 5$, let e be an edge of the star $K_{1,k -2}$ and attaching two vertices at the pendant vertex incident to e. Let T be the graph obtained by subdividing each edge incident to the center. Clearly $\gamma _g(T) = k$ and $\gamma _g(T-e) = k-1$.

Case 2. $\gamma _g(T)-\gamma _g(T-e)=-1$.

For $k=1$, let T be the star $K_{1,t}$. Clearly $\gamma _g(T)=1$ and $\gamma _g(T-e)=2$.

For $k=2$, let T be the graph obtained from $P_3$ by attaching two vertices at one end vertex. Let e be the newly added edge of T. Clearly $\gamma _g(T)=2$ and $\gamma _g(T-e)=3$.

For $k\ge 3$, let T be the graph obtained from the star $K_{1,k}$ by subdividing each edge except one. Let e be the edge that is not subdivided in the star. Clearly $\gamma _g(T)=k$ and $\gamma _g(T-e)=k+1$.

Case 3. $\gamma _g(T)-\gamma _g(T-e)=0$

There is no tree T with an edge e such that $\gamma _g(T)=1$ and $\gamma _g(T-e)=1$. Any tree with $\gamma _g(T)=1$ is of the form $K_{1,k}$ and $\gamma _g(K_{1,k}-e)=2$.

Let e denotes the middle edge of $P_4$ and $\gamma _g(P_4)=\gamma _g(P_4-e)=2$.

For $k \ge 3$, Let T be the graph obtained from $K_{1,k-1}$ by subdividing each edge and e is any pendant edge of T. Clearly $\gamma _g(T)= \gamma _g(T-e) = k$.

Case 4. $\gamma ^{'}_g(T) - {\gamma _g'}(T-e)=1$

For $k=4$, let T be the graph obtained from $P_4$ by attaching three vertices at one of the end points of $P_4$ and let e be the middle edge of $P_4$. Clearly $\gamma ^{'}_g(T)=4$ and $\gamma ^{'}_g(T-e)=3$.

For $k = 5$, let T be the graph obtained from $P_4$ and $K_{1,t}$ by connecting them with an edge e in such a way that one end vertex of e is the degree two vertex of $P_4$ and the other end vertex is any pendant vertex of the star $K_{1,k}$. Clearly $\gamma ^{'}_g(T)=5$ and $\gamma ^{'}_g(T-e)=4$.

For $k\ge 6$, let e be an edge of the star $K_{1,k -3}$ and let T be the graph obtained from the star $K_{1,k -3}$ by subdividing each of its edge and attach three vertices to pendant vertex of the subdivided edge. Clearly $\gamma ^{'}_g(T)=k$ and $\gamma ^{'}_g(T-e)=k-1$.

Case 5. $\gamma ^{'}_g(T) - {\gamma _g'}(T-e) = -1$.

Let T be the graph obtained from $K_2$ by removing its edge. Clearly $\gamma ^{'}_g(T-e)=2$.

For $k=2$, $P_4$ is the graph with $\gamma ^{'}_g(P_4) = 2$ and let T be the graph obtained from $P_4$ by removing its pendant edge. Clearly $\gamma ^{'}_g(T-e)= 3$.

For $k=3$, let T be the graph obtained from $P_3$ by attaching three vertices at one of the end points of $P_3$. Clearly $\gamma ^{'}_g(T)=3$. If e is any pendant edge incident to the highest degree vertex of T then $\gamma ^{'}_g(T-e) = 4$.

For $k\ge 4$, let T be the graph obtained from a star $K_{1, k -2}$ by subdividing each edge except one and attaching three vertices at the end vertex of the edge which is not subdivided. In this case $\gamma ^{'}_g(T)=k$. Ife is the edge incident to one of the new vertices attached. Clearly $\gamma ^{'}_g(T-e)= k+1$.

Case 6: $\gamma ^{'}_g(T)-{\gamma _g'}(T-e)=0$

For $k \ge 2$, let T be the graph obtained from $K_{1,k -1}$ by subdividing each edge. Clearly $\gamma ^{'}_g(T)=k$. If e is any pendant edge then $\gamma ^{'}_g(T-e) = k+1$.

For $k=1$, there is no tree with $\gamma ^{'}_g(T)=1$ and $\gamma ^{'}_g(T)-{\gamma _g'}(T-e)=0$.

3.2 Vertex Removal

Here, we consider the effect of vertex removal in trees. It may be noted that, there are trees T whose game domination number becomes arbitrarily large after removing a vertex from T. It is proved [2] that there is no graph G with $\gamma _g(G)=k$ and $\gamma _g(G-v)=k-2$ for $k\le 4$. We give examples of trees with $\gamma _g(T) = k$ and $\gamma _g(T-v)= k-t$ for any $t \in \{0,1,2\}$ and any integer $k \ge 5$.

Proposition 1

For any $k \ge 5$ there exists a tree T with a vertex v such that $\gamma _g(T)=k$ and $\gamma _g(T-v)=k-2$.

Proof

Let T be a tree obtained from $K_{1,k-2}$ with v as its center in which each edge is subdivided and two vertices are attached at an end vertex u of one subdivided edge as in Fig. 1.

Fig. 1.

A tree T with $\gamma _g(T)=7$ and $\gamma _g(T-v)=5$

Dominator first chooses the vertex v. So $\gamma _g(T)\le 1+\gamma ^{'}_g(T-v|N(v))$ and $\gamma ^{'}_g(T-v|N(v))= 2 + k - 3$. Therefore $\gamma _g(T)\le k$. Dominator never chooses a pendant vertex in T. Suppose that Dominator first chooses a vertex other than v and if it is u then Staller chooses the vertex adjacent to both u and v in T. In this case the game ends with atleast k moves. Suppose that Dominator’s first turn is neither u nor v in T. In this case, Staller chooses a pendant vertex adjacent to u. If second move of Dominator is u then the game ends with atleast k moves. If second move of Dominator is a vertex other than u, then Staller chooses the other pendant vertex adjacent to u. In this case, the game ends with atleast k moves and hence the game domination number of T is k. Dominator first chooses the vertex u in $T-v$, after that Staller and Dominator alternately chooses a vertex from each component. So, the game on $T-v$ has $k-2$ steps and hence $\gamma _g(T-v)= k-2$.

Proposition 2

For any $k \ge 1$ there exists a tree T with $\gamma _g(T) = k$ and $\gamma _g(T-v) = k-1$ for some vertex $v \in V(T)$.

Choose $T = P_n,$ $n \ge 1$. This satisfies the above proposition, as mentioned in [2].

Proposition 3

For any $k \ge 1$ there exists a tree T with $\gamma _g(T) = k$ and $\gamma _g(T-v) = k$ for some vertex $v \in V(T)$.

Proof

Let k be a positive integer and let $T'$ be an arbitrary tree with $\gamma _g(T')=k$ [4]. Let x be a first optimal move of Dominator in $T'$. Let T be the tree obtained from $T'$ by attaching a vertex u to x [2]. In that case, T and $T-u$ have the same game domination number.

Proposition 4

For any $k \ge 1$ there exists a tree T with $\gamma ^{'}_g(T) = k$ and $\gamma ^{'}_g(T-v) = k$ for some vertex $v \in V(T)$.

Proof

Let T be a tree obtained from the star $K_{1,k-1}~(k \ge 2 )$ by subdividing each edge. Let v be an end vertex of any subdivided edge. Then $\gamma ^{'}_g(T) = k$ and $\gamma ^{'}_g(T - v) = k$.

$K_2$ satisfies the desired property for $k=1$.

Proposition 5

For any $k \ge 1$ there exists a tree T with $\gamma ^{'}_g(T)=k$ and $\gamma ^{'}_g(T-v) = k-1$

Proof

Consider the star $K_{1, k-1}~(k \ge 2 )$ and let v be the center of the star. Let T be a tree obtained from this star by subdividing each edge. Clearly, $\gamma ^{'}_g(T) = k$ and $\gamma ^{'}_g(T - v) = k-1$.

$K_1$ satisfies the desired property for $k=1$.

Remark 1

It is proved [2] that there is no graph G with $\gamma ^{'}_g(G) = k$ and $\gamma ^{'}_g(G-v) = k-2$ for $k < 4$ and there exist graphs G with $\gamma ^{'}_g(G)=k$ and $\gamma ^{'}_g(G-v) = k-2$ for $k \ge 4$.

Proposition 6

There is no tree T with $\gamma ^{'}_g(T) = 4$ and $\gamma ^{'}_g(T-v)=2$ for any vertex $v\in T$.

Proof

Assume the contradiction. Let T be a tree with a vertex v such that $\gamma ^{'}_g(T)=4$ and $\gamma ^{'}_g(T-v)=2$. First, consider the case that v is a pendant vertex. Since T is a tree and tree is a no-minus graph [8], so $\gamma ^{'}_g(T)-1\le \gamma ^{'}_g(T-v)\le \gamma ^{'}_g(T)$. Therefore $\gamma ^{'}_g(T)$ is at most 3 and this contradicts $\gamma ^{'}_g(T)=4$. Now, consider the case that v is a cut vertex. In this case $T-v$ is disconnected with exactly two components. If $T-v$ has more than two components then Staller start game domination number of $T-v$ is at least 3. This is not possible. So clearly $T-v$ has exactly two components $T_1$ and $T_2$. Each component is either $K_1$ or $K_2$, otherwise it contradicts that $\gamma ^{'}_{g}(T-v)$ is 2. Since T is a tree, v is adjacent to exactly one vertex in each component. In this case $\gamma ^{'}_g(T)$ is at most 3. This contradicts that $\gamma ^{'}_g(T)=4$.

Fig. 2.

A tree T with $\gamma ^{'}_g(T) = 8$ and $\gamma ^{'}_g(T - v) = 6$

Proposition 7

There is no tree with $\gamma ^{'}_g(T)=5$ and $\gamma ^{'}_g(T-v)=3$ for any vertex v in T.

Proof

Assume the contradiction. Let T be a tree with a vertex v such that $\gamma ^{'}_g(T)=5$ and $\gamma ^{'}_g(T-v)=3$. Removal of a pendant vertex from a tree decreases its game domination number by at most 1. So clearly v is a cut vertex and $T-v$ has at most 3 components. Now, we prove that the vertex v is not an optimal first move of Staller in T. If possible let v be an optimal first move of Staller in T. Then

$$\begin{aligned} \gamma ^{'}_g(T)&= 1+ \gamma _g(T|N[v])\\&\le 1+ \gamma ^{'}_g(T|N[v])\\&= 1+\gamma ^{'}_g(T-v|N(v))\\&\le 1+ \gamma ^{'}_g(T-v).\\ \end{aligned}$$

Hence, Staller start game domination number of $T-v$ is decreased by at most 1. First, we consider the case that $T-v$ has 3 components. In this case each component is either $K_1$ or $K_2$. Staller first chooses a vertex from any of the three components and then Dominator chooses v. In this case the game is finished in at most 4 steps. This contradicts that $\gamma ^{'}_g(T)=5$.

Now consider the case that $T-v$ has exactly two components say $T_1$ and $T_2$. In this case one component say $T_1$ has $\gamma ^{'}_{g}(T_1)=1$ and the other component $T_2$ has $\gamma ^{'}_g(T_2)=2$. So $T_1$ is either $K_1$ or $K_2$ and there is a vertex in $T_2$ which is adjacent to all undominated vertices in $T_2$ after the first move of Staller. Consider a staller start game played on T and first optimal move of Staller is from either $T_1$ or $T_2$. If the first optimal move is from $T_1$ then Dominator chooses v after that Staller chooses a vertex from $T_2$ and Dominator chooses a vertex from $T_2$ that dominates all the undominated vertices in T. So the game on T is finished in at most 4 steps. This contradicts $\gamma ^{'}_g(T)=5$. If the first optimal move is from $T_2$ then Dominator chooses a vertex which is adjacent to all the undominated vertices in $T_2$. After that, Staller chooses a vertex from T and if with this move the game is not yet over, Dominator chooses a vertex in $T_2$ which is adjacent to v. So, the game is finished in at most 4 steps. This is a contradiction. So there is no tree with $\gamma ^{'}_g(T)=5$ and $\gamma ^{'}_g(T-v)=3$.

Proposition 8

For any $k \ge 6$ there exists a tree T with a vertex v such that $\gamma ^{'}_g(T)=k$ and $\gamma ^{'}_g(T-v)=k-2$.

Proof

Let T be the tree obtained from a $K_{1, k-3}$ by subdividing each edge where v as the center of $K_{1, k-3}$ and attaching three vertices to one of the end points say u of a subdivided edge as in Fig. 2. Clearly, $\gamma ^{'}_g(T)=k$ and $\gamma ^{'}_g(T-v)=k-2$.