Properties of the Global Total k-Domination Number

Abstract

A nonempty subset $D\subset V$ of vertices of a graph $G=(V,E)$ is a dominating set if every vertex of this graph is adjacent to at least one vertex from this set except the vertices which belong to this set itself. $D\subseteq V$ is a total k-dominating set if there are at least k vertices in set D adjacent to every vertex $v\in V$, and it is a global total k-dominating set if D is a total k-dominating set of both G and $\overline{G}$. The global total k-domination number of G, denoted by ${\gamma }_{kt}^g\left(G\right)$, is the minimum cardinality of a global total k-dominating set of G, GTkD-set. Here we derive upper and lower bounds of ${\gamma }_{kt}^g\left(G\right)$, and develop a method that generates a GTkD-set from a GT$(k-1)$D-set for the successively increasing values of k. Based on this method, we establish a relationship between ${\gamma }_{(k-1)t}^g\left(G\right)$ and ${\gamma }_{kt}^g\left(G\right)$, which, in turn, provides another upper bound on ${\gamma }_{kt}^g\left(G\right)$.

1. Introduction

We start by introducing the basic notation. Suppose we are given a simple graph $G=(V,E)$ with $\left|V\right|=n$ (n is called the order of graph G) and $\left|E\right|=m$ (m is called the size of graph G). Given $D\subseteq V$ ($D\ne \varnothing$) and vertex $v\in V$, let $N_D\left(v\right)$ be the set of all vertices from set D, adjacent to vertex v (also called the neighbors of vertex v from set D); we will use ${\overline{N}}_D\left(v\right)$ for the set of vertices in set D which are not neighbors of vertex v (${\overline{N}}_D\left[v\right]={\overline{N}}_D\left(v\right)\cup \left\{v\right\}$). We let $N_D\left[v\right]=N_D\left(v\right)\cup \left\{v\right\}$, and we call ${\delta }_D\left(v\right)=\left|N_D\left(v\right)\right|$ the degree of vertex v in set D. We denote by ${\overline{\delta }}_D\left(v\right)$ the cardinality of set ${\overline{N}}_D\left(v\right)$ (${\overline{\delta }}_D\left(v\right)=\left|{\overline{N}}_D\left(v\right)\right|$). We will use more compact notation $N\left(v\right)$, $N\left[v\right]$, $\delta \left(v\right)$, $\overline{N}\left(v\right)$ and $\overline{N}\left[v\right]$ instead of $N_G\left(v\right)$, $N_G\left[v\right]$, ${\delta }_G\left(v\right)$, ${\overline{N}}_G\left(v\right)$ and ${\overline{N}}_G\left[v\right]$, respectively, when this will cause no confusion. The minimum (the maximum, respectively) degree in graph G is traditionally denoted by $\delta$ ($\Delta$, respectively). $G\left[S\right]$ and $\overline{G}$, respectively, will stand for the subgraph of graph G induced by $S\subseteq V$ and the complement of graph G, respectively.

Let X and Y be subsets of set V. We denote by $E(X,Y)$ the set of all the edges in graph G joining a vertex $x\in X$ with a vertex $y\in Y$. Let u and v be vertices from set V. Then the distance between these two vertices $d(u,v)$ is the length (the number of edges) of a minimum $u-v$-path. The length of the longest $u-v$ path, for any u and v, is called the diameter of graph G, denoted by $diam\left(G\right)$. The girth of graph G is the length of the shortest cycle in that graph and is denoted by $g\left(G\right)$.

Let $D\subseteq V$ be a nonempty subset of set V. Then D is called a total k-dominating set for graph G if there are at least k vertices in set D adjacent to every vertex $v\in V$ (we will also say that vertex v is totally k-dominated by set D). The cardinality of a total k-dominating set in graph G with the minimum cardinality is called the total k-domination number of graph G and is denoted by ${\gamma }_{kt}\left(G\right)$. We will refer to a total k-dominating set with cardinality ${\gamma }_{kt}\left(G\right)$ as a ${\gamma }_{kt}\left(G\right)$-set. A total 1-dominating set is normally referred to as a total dominating set, and the total 1-domination number is referred to as the total domination number, denoted by ${\gamma }_t\left(G\right)$. We refer the reader to [1,2,3,4,5,6,7,8,9] for more detail on these definitions.

Given again a non-empty set $D\subseteq V$, D is called a global total k-dominating set of graph G (GTkD set for short) if D is a total k-dominating set of both graphs G and $\overline{G}$. The global total k-domination number of G, denoted by ${\gamma }_{kt}^g\left(G\right)$, is the cardinality of a global total k-dominating set with the minimum cardinality. A global total k-dominating set of cardinality ${\gamma }_{kt}^g\left(G\right)$ will be referred to as a ${\gamma }_{kt}^g\left(G\right)$-set. Again, if $k=1$, a global total 1-dominating set is a global total dominating set (see [10,11]).

As it is well-known and also easily be seen,

$$2k+1\le {\gamma }_{kt}^g\left(G\right)\le n,$$

for any graph G with order n. Here we shall exclusively deal with the connected graphs due to a known fact that if $G_1,G_2,\dots ,G_r$ ($r\ge 2$) are the connected components in graph G, then

$${\gamma }_{kt}^g\left(G\right)=\sum _{i=1}^r{\gamma }_{kt}\left(G_i\right)$$

(see [12]).

The main goal of this paper is to complete the current study of global total k-domination number in graphs. First, we give upper and lower bounds on ${\gamma }_{kt}^g\left(G\right)$, and then we develop a method that generates a GTkD-set from a GT$(k-1)$D-set for the successively increasing values of k. Based on this method, we establish a relationship between ${\gamma }_{(k-1)t}^g\left(G\right)$ and ${\gamma }_{kt}^g\left(G\right)$, which, in turn, provides another upper bound on ${\gamma }_{kt}^g\left(G\right)$.

The rest of the paper is organized as follows. In the next section, we present known results and give some remarks. In Section 3 and Section 4, we derive upper and lower bounds, respectively, for global total k-domination number. In the Section 5, we provide our method that obtains a global total $(k+1)$-dominating set from a global total k-dominating set.

2. Relations between ${\gamma }_{kt}^g\left(G\right)$ and ${\gamma }_{kt}\left(G\right)$

Clearly, the definition of a GTkD set gives us an implicit lower bound for the parameter ${\gamma }_{kt}^g\left(G\right)$:

Observation 1.

Let G be a graph; then ${\gamma }_{kt}^g\left(G\right)\ge max\{{\gamma }_{kt}\left(G\right),{\gamma }_{kt}\left(\overline{G}\right)\}$.

The above lower bound is not necessarily attainable, as we illustrate in the following figure: we depict graph G and its complement $\overline{G}$, and the corresponding minimum total 2-dominating set in both graphs (black vertices); see Figure 1.

The following proposition was proved in [12].

Proposition 1.

Let G be a graph,

(i)

If ${\gamma }_{kt}\left(G\right)>\Delta \left(G\right)+k$, then ${\gamma }_{kt}^g\left(G\right)={\gamma }_{kt}\left(G\right)$.

(ii)

If ${\gamma }_{kt}\left(G\right)\le \Delta \left(G\right)+k$, then ${\gamma }_{kt}^g\left(G\right)\le \Delta \left(G\right)+k+1$.

Corollary 1.

Let G be a graph with maximum degree Δ. Then, ${\gamma }_{kt}^g\left(G\right)\le max\{{\gamma }_{kt}\left(G\right),\Delta +k+1\}$.

Proposition 2.

Let G be a graph with order n and maximum degree Δ. If $n>\frac{\Delta (\Delta +k)}{k}$, then ${\gamma }_{kt}^g\left(G\right)={\gamma }_{kt}\left(G\right)$.

Proof. 

If $n>\frac{\Delta (\Delta +k)}{k}$, then $\Delta +k<\frac{kn}{\Delta }\le {\gamma }_{kt}\left(G\right)$; consequently, $\Delta +k+1\le {\gamma }_{kt}\left(G\right)$. By Corollary 1 we have ${\gamma }_{kt}^g\left(G\right)={\gamma }_{kt}\left(G\right)$. □

Theorem 1.

For any graph G, ${\gamma }_{kt}^g\left(G\right)={\gamma }_{kt}\left(G\right)$ if and only if there exists a minimum total k-dominating set D such that any subset $D^{\prime }$ of D with $\left|D\right|-k+1$ vertices is not included in any star in the graph—that is, and only if there is not a vertex $v\in V$ such that $D^{\prime }\subseteq N\left[v\right]$.

Proof. 

Let D be a minimum total k-dominating set which is also a global total k-dominating set, and let $D^{\prime }$ be a subset of D with cardinality $\left|D\right|-k+1$. If there exists a vertex $v\in V$ such that $D^{\prime }\subseteq N\left[v\right]$, then $v\in D^{\prime }$ and it is adjacent to $\left|D\right|-k$ vertices in $D^{\prime }$, so v has less than k non-adjacent vertices in D, or $v\notin D^{\prime }$, and it is adjacent to $\left|D\right|-k+1$ vertices in $D^{\prime }$, so v has less than k non-adjacent vertices in D. In both cases we have a contradiction with the fact that D is a global total k-dominating set.

On the other hand, we take a minimum total k-dominating set D such that for any subset $D^{\prime }$ of D with $\left|D\right|-k+1$ vertices and every vertex $v\in V$, we have $D^{\prime }⊈N\left[v\right]$. Then, for any vertex $v\in D$ we have $\left|N\right(v\left)\right|<\left|D\right|-k$, so v has, at least, k non-neighbors in D. If $v\in V\backslash D$ we have $\left|N\right(v\left)\right|<\left|D\right|-k+1$, so v has, at least, k non-neighbors in D. Therefore, D is a global total k-dominating set. □

3. Upper Bounds for the Global Total k-Domination Number

In this section, we obtain some upper bounds for the global total k-domination number in a graph. Bermudo et al. in [12] showed a characterization when the global total k-domination number is equal to the order of the graph, but we give here that characterization in a more specific way. To do that, in the following proposition we give a condition to guarantee that the global total k-domination number is less than n.

Proposition 3.

Let G be a graph with order n, minimum degree δ and maximum degree Δ. If $k<\min \{\delta ,n-\Delta -1\}$, then ${\gamma }_{kt}^g\left(G\right)\le n-1$.

Proof. 

Let us see that, for any $v\in V$, the set $D=V\backslash \left\{v\right\}$ is a GTkD set of G. We have that ${\delta }_D\left(v\right)=\delta \left(v\right)\ge \delta >k$ and ${\overline{\delta }}_D\left(v\right)=n-1-\delta \left(v\right)\ge n-1-\Delta >k$. For every $u\in D$ we have ${\delta }_D\left(u\right)\ge \delta \left(u\right)-1\ge \delta -1\ge k$ and ${\overline{\delta }}_D\left(u\right)\ge n-1-\delta \left(u\right)-1\ge n-2-\Delta \ge k$. Therefore, D is a GTkD set of G. □

Proposition 3 is not an equivalence, as we can see if we consider a triangle and we add a leaf to every vertex of the triangle. In such a case ${\gamma }_{1t}^g\left(G\right)\le n-1=5$ and $k=1=\min \{\delta ,n-\Delta -1\}$.

Now, in order to present the characterization of all graphs having a global total k-domination number equal to the number of vertices, we need to define the following set. Given a graph G and an integer i, let $T_i\left(G\right)=\{v\in V\left(G\right):\delta \left(v\right)=i\}$ (i.e., the set of vertices in graph G with the degree i).

Theorem 2.

Given graph G with order n and the minimum and the maximum degrees δ and Δ, ${\gamma }_{kt}^g\left(G\right)=n$ if and only if one of the conditions (a)–(c) below hold

(a)

$k=\delta <n-\Delta -1$ and ${\displaystyle V=\bigcup _{v\in T_{\delta }\left(G\right)}N\left(v\right)}$.

(b)

$k=n-\Delta -1<\delta$ and ${\displaystyle V=\bigcup _{w\in T_{\Delta }\left(G\right)}(V\backslash N\left[w\right])}$.

(c)

$k=\delta =n-\Delta -1$ and ${\displaystyle V=\left(\bigcup _{v\in T_{\delta }\left(G\right)}N\left(v\right)\right)\cup \left(\bigcup _{w\in T_{\Delta }\left(G\right)}(V\backslash N\left[w\right])\right)}$.

Proof. 

(a) If $k=\delta <n-\Delta -1$ and ${\displaystyle V=\bigcup _{v\in T_{\delta }\left(G\right)}N\left(v\right)}$, we consider $D=V\backslash \left\{u\right\}$ for any $u\in V$. We note that there exists $v\in N\left(u\right)$ such that $\delta \left(v\right)=k$; this implies that ${\delta }_D\left(v\right)<k$. Thus, D is not a GTkD set of G. Hence, ${\gamma }_{kt}^g\left(G\right)=n$.

(b) If $k=n-\Delta -1<\delta$ and ${\displaystyle V=\bigcup _{w\in T_{\Delta }\left(G\right)}(V\backslash N\left[w\right])}$, for any $u\in V$ there exists $w\in V$ such that $\delta \left(w\right)=\Delta$ and $u\notin N\left[w\right]$. If we consider $D=V\backslash \left\{u\right\}$, then ${\overline{\delta }}_D\left(w\right)\le n-\Delta -2<k$; thus, D is not a GTkD set of G. Therefore, ${\gamma }_{kt}^g\left(G\right)=n$.

(c) If $k=\delta =n-\Delta -1$ and ${\displaystyle V=\left(\bigcup _{v\in T_{\delta }\left(G\right)}N\left(v\right)\right)\cup \left(\bigcup _{w\in T_{\Delta }\left(G\right)}(V\backslash N\left[w\right])\right)}$, using (a) or (b), we obtain that $V\backslash \left\{u\right\}$ is not a GTkD set of G, for any $u\in V$. Consequently, ${\gamma }_{kt}^g\left(G\right)=n$.

Finally, if we assume that ${\gamma }_{kt}^g\left(G\right)=n$, by Proposition 3 we have that $k\in \{\delta ,n-\Delta -1\}$. For every vertex $v\in V$, we note that $D=V\backslash \left\{v\right\}$ is not a GTkD set of G, so there exists $u\in D$ such that ${\delta }_D\left(u\right)<k$ or ${\overline{\delta }}_D\left(u\right)<k$. If $k=\delta <n-\Delta -1$, since ${\overline{\delta }}_D\left(u\right)\ge n-2-\delta \left(u\right)\ge n-2-\Delta \ge k$, then we have that ${\delta }_D\left(u\right)<k=\delta$; this implies that $u\in T_{\delta }\left(G\right)$ and $v\in N\left(u\right)$. If $k=n-\Delta -1<\delta$, since ${\delta }_D\left(u\right)\ge \delta \left(u\right)-1\ge \delta -1\ge k$, then we have that $n-2-\delta \left(u\right)\le {\overline{\delta }}_D\left(u\right)<k=n-\Delta -1$; that is, $n-2-\delta \left(u\right)={\overline{\delta }}_D\left(u\right)=n-\Delta -2$, so $u\in T_{\Delta }\left(G\right)$ and $v\in V\backslash N\left[u\right]$. If $k=\delta =n-\Delta -1$, since ${\delta }_D\left(u\right)<k$ or ${\overline{\delta }}_D\left(u\right)<k$, we have that $u\in T_{\delta }\left(G\right)$ and $v\in N\left(u\right)$, or $u\in T_{\Delta }\left(G\right)$ and $v\in V\backslash N\left[u\right]$. □

The following corollary was directly obtained from Theorem 2.

Corollary 2.

Let G be a graph with minimum degree δ, maximum degree Δ and order $n\ne \Delta +\delta +1$. Then ${\gamma }_{kt}^g\left(G\right)=n$ if and only if one of the following condition holds.

(a)

$k=\delta <n-\Delta -1$ and ${\gamma }_{kt}\left(G\right)=n$.

(b)

$k=n-\Delta -1<\delta$ and ${\gamma }_{kt}\left(\overline{G}\right)=n$.

Corollary 3.

Let G be a graph of order n, minimum degree δ and maximum degree Δ. If one of the following conditions holds:

(a)

$k=\delta <n-\Delta -1$ and $|T_{\delta }\left(G\right)|\ge n-\delta$.

(b)

$k=n-\Delta -1<\delta$ and $|T_{\Delta }\left(G\right)|\ge \Delta +1$

(c)

$k=\delta =n-\Delta -1$ and $|T_{\delta }\left(G\right)|\ge n-\delta$ or $|T_{\Delta }\left(G\right)|\ge \Delta +1$,

then ${\gamma }_{kt}^g\left(G\right)=n$.

Proof. 

Since ${\gamma }_{kt}^g\left(G\right)={\gamma }_{kt}^g\left(\overline{G}\right)$, $\overline{\Delta }=n-\delta -1$, $T_{\overline{\Delta }}\left(\overline{G}\right)=T_{\delta }\left(G\right)$ and $V\backslash N_{\overline{G}}\left[w\right]=N\left(w\right)$, it is enough to check that $|T_{\Delta }\left(G\right)|\ge \Delta +1$ implies $V={\bigcup }_{w\in T_{\Delta }\left(G\right)}(V\backslash N\left[w\right])$. However, for any vertex $v\in V$, if $|T_{\Delta }\left(G\right)|\ge \Delta +1$, then there exists a vertex $w\in T_{\Delta }\left(G\right)$ which is not a neighbor of v, so $v\in {\bigcup }_{w\in T_{\Delta }\left(G\right)}(V\backslash N\left[w\right])$. □

It was proved in [12] that ${\gamma }_{kt}^g\left(G\right)\le \min \left\{{\gamma }_{kt}\left(G\right)+\Delta ,{\gamma }_{kt}\left(G\right)+{\gamma }_{kt}\left(\overline{G}\right)\right\}$. It would be convenient to characterize the graphs G such that ${\gamma }_{kt}^g\left(G\right)={\gamma }_{kt}\left(G\right)+\Delta$, and the graphs G such that ${\gamma }_{kt}^g\left(G\right)={\gamma }_{kt}\left(G\right)+{\gamma }_{kt}\left(\overline{G}\right)$. On the other hand, the invariants of a graph are important when characterizing them; below we use some of them such as diameter and girth. The following proofs use the ideas showed in [11].

Theorem 3.

If G is a graph such that $diam\left(G\right)\ge 5$, every total k-dominating set is a GTkD set of G.

Proof. 

Let D be a total k-dominating set and $u,v\in V$ such that $d(u,v)\ge 5$. Since ${\delta }_D\left(u\right)\ge k$ and ${\delta }_D\left(v\right)\ge k$, there exist $\{u_1,\dots ,u_k\}\subseteq D\cap N\left(u\right)$ and $\{v_1,\dots ,v_k\}\subseteq D\cap N\left(v\right)$. For any vertex $w\in V$ we know that ${\delta }_D\left(w\right)\ge k$. If $u_i\in N\left(w\right)$ for some $i\in \{1,\dots ,k\}$, then ${\displaystyle w\notin \bigcup _{i=1}^{k}N\left[v_i\right]}$; that means, ${\overline{\delta }}_D\left(w\right)\ge k$. Therefore, D is a GTkD set of G. □

Corollary 4.

If G is a graph such that $diam\left(G\right)\ge 5$, then ${\gamma }_{kt}^g\left(G\right)={\gamma }_{kt}\left(G\right)$.

According to the idea given in [11], we obtain the following result.

Proposition 4.

If G is a graph such that $diam\left(G\right)=4$ and there exist $\{u,v_1,\dots ,v_k\}\subseteq V$ such that $dist(u,v_j)=4$ for every $j\in \{1,\dots ,k\}$, then ${\gamma }_{kt}^g\left(G\right)\le {\gamma }_{kt}\left(G\right)+k$.

Proof. 

Let D be a minimum total k-dominating set of a graph; then there exists the vertex set $\{u_1,\dots ,u_k\}\subseteq D$ such that $\{u_1,\dots ,u_k\}\subseteq N\left(u\right)$. For any vertex $w\in V$ and $i\in \{1,\dots ,k\}$, w cannot be adjacent to both $u_i$ and $v_i$, so $D\cup \{v_1,\dots ,v_k\}$ is a global total k-dominating set. □

In Figure 2 we can see an example where the equality in Proposition 4 for $k=2$ is attained. Taking into account that any neighbor of a vertex of degree 2 must belong to any total 2-dominating set (grey vertices), we show in that figure the minimum total 2-dominating set (b) and the minimum global total 2-dominating set (c).

For a graph G, we let ${\delta }^{*}\left(G\right)=min\{\delta \left(G\right),\delta \left(\overline{G}\right)\}$.

Proposition 5.

Let G be a graph of order n and minimum degree δ; then ${\gamma }_{kt}^g\left(G\right)\le n-{\delta }^{*}\left(G\right)+k$.

Proof. 

Let us see that every set $D\subseteq V$ such that $\left|D\right|\ge n-{\delta }^{*}\left(G\right)+k$ is a global total k-dominating set. Since $\left|D\right|\ge n-\delta +k$, every vertex v satisfies ${\delta }_{V\backslash D}\left(v\right)\le \delta -k$, ${\delta }_D\left(v\right)\ge k$. Since $\left|D\right|\ge n-\overline{\delta }+k$, every vertex v satisfies ${\overline{\delta }}_{V\backslash D}\left(v\right)\le \overline{\delta }-k$, so ${\overline{\delta }}_D\left(v\right)\ge k$. □

4. Lower Bounds for the Global Total k-Domination Number

We know that any graph G satisfies ${\gamma }_{kt}^g\left(G\right)\ge 2k+1$, and a characterization for graphs satisfying the equality was given in [12]. Additionally, in that work the authors showed the following inequality.

Remark 1.

Let G be a graph with order n, minimum degree δ and maximum degree Δ. Then,

$${\gamma }_{kt}^g\left(G\right)\ge max\left\{\frac{kn}{\Delta },\frac{kn}{n-\delta -1}\right\}$$

For example, the lower bound given above can be reached in the graph shown in Figure 3.

Theorem 4.

Let G be a graph of order n, maximum degree Δ and size m. Then

$${\gamma }_{kt}^g\left(G\right)\ge \frac{2m+n(2k-\Delta )+{(2k+1)}^2}{n+2k}.$$

Proof. 

Let D be a ${\gamma }_{kt}\left(G\right)$-set. Since every vertex in $V\backslash D$ cannot have more that $\left|D\right|-k$ neighbors in D, we have $E(D,V\backslash D)\le (n-|D\left|\right)\left(\right|D|-k)$, so

$$\begin{array}{ccc}\hfill m& =& E(D,D)+E(D,V\backslash D)+E(V\backslash D,V\backslash D)\hfill \\ & \le & \frac{\left|D\right|\Delta \left(G\right)-E(D,V\backslash D)}{2}+E(D,V\backslash D)+\frac{(\Delta -k)(n-|D\left|\right)}{2}\hfill \\ & \le & \frac{\left|D\right|\Delta +(n-|D\left|\right)\left(\right|D|-k)+(\Delta -k)(n-|D\left|\right)}{2}\hfill \\ & =& \frac{\left|D\right|\Delta +(n-|D\left|\right)\left(\right|D|-2k+\Delta )}{2}\hfill \\ & =& \frac{-{\left|D\right|}^2+(n+2k)\left|D\right|+n\Delta -2kn}{2},\hfill \end{array}$$

which implies that

$$\begin{array}{c}\hfill {(2k+1)}^2+2m\le {\left|D\right|}^2+2m\le (n+2k)\left|D\right|+n\Delta -2kn,\end{array}$$

then

$$\left|D\right|\ge \frac{2m+n(2k-\Delta )+{(2k+1)}^2}{n+2k}.$$

 □

Theorem 5.

Let G be a graph with order n, maximum degree Δ and size m. Then,

$${\gamma }_{kt}^g\left(G\right)\ge \frac{2m+n(\Delta -2k)}{n+k-\Delta }.$$

Proof. 

We suppose that D is a ${\gamma }_{kt}\left(G\right)$-set and $\left|D\right|\ge 2r+1$ for some $r\ge 2$, and $\left|D\right|\ge 2k+2$. Since D is minimal, for any vertex $v_1\in D$ there exists a vertex $w_{v_1}$ such that one of the following conditions holds.

(1)

$w_{v_1}\in D$, $v_1\in N\left(w_{v_1}\right)$ and ${\delta }_D\left(w_{v_1}\right)=k$,

(2)

$w_{v_1}\in D$, $v_1\notin N\left(w_{v_1}\right)$ and ${\delta }_D\left(w_{v_1}\right)=\left|D\right|-k-1$,

(3)

$w_{v_1}\in V\backslash D$, $v_1\in N\left(w_{v_1}\right)$ and ${\delta }_D\left(w_{v_1}\right)=k$,

(4)

$w_{v_1}\in V\backslash D$, $v_1\notin N\left(w_{v_1}\right)$ and ${\delta }_D\left(w_{v_1}\right)=\left|D\right|-k$.

Now, in cases (1) and (3), we take $v_2\in D\backslash N\left(w_{v_1}\right)$, and in cases (2) and (4), we take $v_2\in D\cap N\left(w_{v_1}\right)$, and we know that there exists a vertex $w_{v_2}\ne w_{v_1}$ such that one of the above conditions holds. Since $\left|D\right|\ge 2r+1$ we can obtain $w_{v_1},\dots ,w_{v_r}$ vertices satisfying one of the conditions above. We suppose that there exist i, $j-i$, s and $r-j-s$ vertices satisfying (1), (2), (3) and (4), respectively. Then,

$$\begin{array}{ccc}\hfill E(D,D)& \le & \frac{ik+(j-i)\left(\right|D|-k-1)+\left(\right|D|-j)\left(\right|D|-k-1)}{2}\hfill \\ & =& \frac{ik-i\left(\right|D|-k-1)+\left|D\right|\left(\right|D|-k-1)}{2}\hfill \\ & =& \frac{i(2k-|D|+1)+\left|D\right|\left(\right|D|-k-1)}{2},\hfill \end{array}$$

$$\begin{array}{ccc}\hfill E(D,V\backslash D)& \le & \frac{sk+(r-j-s)\left(\right|D|-k)+(n-|D|-r+j)\left(\right|D|-k)}{2}\hfill \\ & =& \frac{sk-s\left(\right|D|-k)+(n-|D\left|\right)\left(\right|D|-k)}{2}\hfill \\ & =& \frac{(n-|D\left|\right)\left(\right|D|-k)+s(2k-|D\left|\right)}{2},\hfill \end{array}$$

and

$$\begin{array}{ccc}\hfill E(V\backslash D,V\backslash D)& \le & \frac{s(\Delta -k)+(r-j-s)(\Delta -|D|+k)}{2}\hfill \\ & +& \frac{(n-|D|-r+j)(\Delta -k)}{2}\hfill \\ & =& \frac{s(\Delta -k)+(r-j-s)(\Delta -k-|D|+2k)}{2}\hfill \\ & +& \frac{(n-|D|-r+j)(\Delta -k)}{2}\hfill \\ & =& \frac{(\Delta -k)(n-|D\left|\right)+(r-j-s)(2k-|D\left|\right)}{2};\hfill \end{array}$$

therefore,

$$\begin{array}{ccc}\hfill m& \le & E(D,D)+E(D,V\backslash D)+E(V\backslash D,V\backslash D)\hfill \\ & \le & \frac{i(2k-|D|+1)+\left|D\right|\left(\right|D|-k-1)}{2}+\frac{(n-|D\left|\right)\left(\right|D|-k)+s(2k-|D\left|\right)}{2}\hfill \\ & & +\frac{(\Delta -k)(n-|D\left|\right)+(r-j-s)(2k-|D\left|\right)}{2}\hfill \\ & =& \frac{i(2k-|D|+1)+\left|D\right|\left(\right|D|-k-1)}{2}\hfill \\ & +& \frac{(n-|D\left|\right)\left(\right|D|-2k+\Delta )+(r-j)(2k-|D\left|\right)}{2}\hfill \\ & =& \frac{\left|D\right|(n+k-\Delta )+n(-2k+\Delta )+(i+r-j)(2k-|D\left|\right)+i}{2}\hfill \\ & \le & \frac{\left|D\right|(n+k-\Delta )+n(-2k+\Delta )}{2};\hfill \end{array}$$

then

$$\left|D\right|\ge \frac{2m+n(\Delta -2k)}{n+k-\Delta }.$$

 □

Let us see another lower bound using the algebraic connectivity. Given a graph G, its adjacency matrix A and the diagonal matrix D whose entries are the degrees of all vertices in the graph, the Laplacian matrix is defined as $L=A-D$. The algebraic connectivity of G, denoted by $\mu$ is the second smallest eigenvalue of the Laplacian matrix. The algebraic connectivity of $G=(V,E)$ with order n satisfies the following equality given by Fielder [13].

$$\mu =2n\min \left\{\frac{{\sum }_{v_i{v}_j\in E}{(w_i-w_j)}^2}{{\sum }_{v_i\in V}{\sum }_{v_j\in V}{(w_i-w_j)}^2}:w\ne \alpha \mathbf{j}\mathrm{for}\alpha \in \mathbb{R}\right\},$$

where $\mathbf{j}=(1,1,\dots ,1)$ and $w\in {\mathbb{R}}^n$.

Theorem 6.

Let G be a graph with order n and algebraic connectivity μ. Then,

$${\gamma }_{kt}^g\left(G\right)\ge \frac{kn}{n-\mu }.$$

Proof. 

Let D be a ${\gamma }_{kt}\left(G\right)$-set. It can be found that if we take

$$w=\left\{\begin{array}{c}1\mathrm{if}v\in D\\ 0\mathrm{if}v\notin D\end{array}\right.$$

in the set given above, since $\mu$ is the minimum, we have

$$\mu \le \frac{n{\sum }_{v\in D}{\delta }_{\overline{D}}\left(v\right)}{\left|D\right|(n-|D\left|\right)}\le \frac{n(n-|D\left|\right)\left(\right|D|-k)}{\left|D\right|(n-|D\left|\right)}=\frac{n\left(\right|D|-k)}{\left|D\right|};$$

therefore, $\left|D\right|\ge \frac{kn}{n-\mu }$. □

Theorem 7.

Let G be a graph of order n and maximum degree Δ. If $k\ge \min \left\{\frac{\Delta }{2},\frac{n-\delta -1}{2}\right\}$, then

$${\gamma }_{kt}^g\left(G\right)\ge \frac{\sqrt{4kn+1}+1}{2}.$$

Proof. 

Let D be a ${\gamma }_{kt}\left(G\right)$-set. For every $v\in D$, if we suppose that $k\ge \frac{\Delta }{2}$, we have ${\delta }_D\left(v\right)\ge {\delta }_{\overline{D}}\left(v\right)$, then

$$\begin{array}{ccc}\hfill \left|D\right|\left(\right|D|-k-1)& \ge & \sum _{v\in D}{\delta }_D\left(v\right)\ge \sum _{v\in D}{\delta }_{\overline{D}}\left(v\right)\ge (n-|D\left|\right)k,\hfill \end{array}$$

which implies that ${\left|D\right|}^2-\left|D\right|\ge kn$, or equivalently, that ${\left(\left|D\right|-\frac{1}{2}\right)}^2\ge kn+\frac{1}{4}$; that is, $\left|D\right|\ge \frac{\sqrt{4kn+1}+1}{2}$.

If $\frac{n-\delta -1}{2}\le k<\frac{\Delta }{2}$, since ${\gamma }_{kt}^g\left(G\right)={\gamma }_{kt}^g\left(\overline{G}\right)$ and $\overline{\Delta }=n-\delta -1$, we can obtain the same result. □

The lower bound given in Theorem 7 is attained, for instance, in the graph given in Figure 4.

In graph theory, it is common to analyze graphs obtained by some transformation from an originally given graph. An example of such a transformation is the elimination of one or more edges of the graph. Given a graph G, it is natural to think about what happens if you add or delete edges on the graph. We note that removing an edge in G is equivalent to adding an edge to graph $\overline{G}$. Therefore, it suffices to study just one of these cases.

Proposition 6.

Let G be a graph with order n, minimum degree δ and maximum degree Δ, and let $k<min\{\delta ,n-\Delta -1\}$. Then the following inequalities are satisfied (for an edge e):

$${\gamma }_{kt}^g(G-e)\le {\gamma }_{kt}^g\left(G\right)+2,$$

$${\gamma }_{kt}^g(G+e)\le {\gamma }_{kt}^g\left(G\right)+2.$$

Proof. 

Let G be a graph and D be a ${\gamma }_{kt}^g\left(G\right)$-set, and we consider $e\in E$. Notice that $e\in E(V\backslash D,V\backslash D)$, $e\in E(D,V\backslash D)$ or $e\in E(D,D)$; we will divide the proof into three cases and we denote $G^{\prime }=G-e$.

Case 1: If $e\in E(V\backslash D,V\backslash D)$. Note that every vertex in $V\left(G^{\prime }\right)$ has at least k neighbors and k non-neighbors in D. Therefore, ${\gamma }_{kt}^g\left(G^{\prime }\right)\le \left|D\right|={\gamma }_{kt}^g\left(G\right)<{\gamma }_{kt}^g\left(G\right)+2$.

Case 2: If $e\in E(D,V\backslash D)$. Let $e=uv$, where $u\in D$ and $v\in V\backslash D$. We note that for every $w\in V\left(G\right)-\left\{v\right\}$, ${\delta }_D\left(w\right)\ge k$ and ${\overline{\delta }}_D\left(w\right)\ge k$. On the other hand, note that ${\overline{\delta }}_D\left(v\right)>k$ in $G^{\prime }$, and if ${\delta }_D\left(v\right)\ge k$ in $G^{\prime }$, then ${\gamma }_{kt}^g\left(G^{\prime }\right)\le \left|D\right|={\gamma }_{kt}^g\left(G\right)<{\gamma }_{kt}^g\left(G\right)+2$. Now, if ${\delta }_D\left(v\right)=k-1$ in $G^{\prime }$, then there exists $w\in V\left(G^{\prime }\right)\backslash D$ such that $w\in N_{G^{\prime }}\left(v\right)$. Therefore, $D\cup \left\{w\right\}$ is a GTkD set of $G^{\prime }$, so ${\gamma }_{kt}^g\left(G^{\prime }\right)\le |D\cup \left\{w\right\}|={\gamma }_{kt}^g\left(G\right)+1<{\gamma }_{kt}^g\left(G\right)+2$.

Case 3: If $e\in E(D,D)$. Let $e=uv$ where $u,v\in D$. We note that for every $w\in V\left(G\right)-\{u,v\}$, ${\delta }_D\left(w\right)\ge k$ and ${\overline{\delta }}_D\left(w\right)\ge k$. In the worst case ${\delta }_D\left(u\right)<k$ and ${\delta }_D\left(v\right)<k$; the others cases are solved as the above; there exists $w,p\in V\left(G^{\prime }\right)\backslash D$ such that $w\in N_{G^{\prime }}\left(u\right)$ and $p\in N_{G^{\prime }}\left(v\right)$. Now, if $w=p$ then $D\cup \left\{w\right\}$ is a GTkD set of $G^{\prime }$ and ${\gamma }_{kt}^g\left(G^{\prime }\right)\le |D\cup \left\{w\right\}|={\gamma }_{kt}^g\left(G\right)+1<{\gamma }_{kt}^g\left(G\right)+2$; otherwise, $w\ne p$ and then $D\cup \{w,p\}$ is a GTkD set of $G^{\prime }$; hence ${\gamma }_{kt}^g\left(G^{\prime }\right)\le |D\cup \{w,p\}|={\gamma }_{kt}^g\left(G\right)+2$.

Thus, the first inequality is satisfied: ${\gamma }_{kt}^g(G-e)\le {\gamma }_{kt}^g\left(G\right)+2$. Now, as we say above for this problem, removing an edge in G is analogous to adding an edge in $\overline{G}$. Since $G-e$ and $\overline{G}+e$ are complementary graphs and it is known that ${\gamma }_{kt}^g\left(\overline{G}\right)={\gamma }_{kt}^g\left(G\right)$, it is verified that ${\gamma }_{kt}^g(G-e)={\gamma }_{kt}^g(\overline{G}+e)$. Hence, by the first inequality ${\gamma }_{kt}^g(\overline{G}+e)={\gamma }_{kt}^g(G-e)\le {\gamma }_{kt}^g\left(G\right)+2={\gamma }_{kt}^g\left(\overline{G}\right)+2$. So, ${\gamma }_{kt}^g(G+e)\le {\gamma }_{kt}^g\left(G\right)+2$. □

Let S be a subset of set V such that the maximum degree of the subgraph induced by the vertices from set S is no more than $k-1$. Then set S will be referred to as a k-independent set of vertices. The cardinality of a k-independent set of the maximum cardinality will be referred to as the k-independence number in graph G and will be denoted by ${\beta }_k\left(G\right)$. The lower k-independence number $i_k\left(G\right)$ is the minimum cardinality of a maximal k-independent set in graph G.

Proposition 7.

Let D be a global total k-dominating set in G and let $V\backslash D$ be a maximum $(\Delta -k)$-independent. Then,

$$n-{\beta }_{\Delta -k}\left(G\right)\le \left|D\right|\le \min \{n-\gamma \left(G\right),n-i_{\Delta -k}\left(G\right)\}.$$

Proof. 

Since $V\backslash D$ is a maximal $(\Delta -k)$-independent set, $V\backslash D$ is a dominating set; thus, $n-\left|D\right|\ge \gamma \left(G\right)$. Moreover, $i_{\Delta -k}\left(G\right)\le n-\left|D\right|\le {\beta }_{\Delta -k}\left(G\right)$. □

5. Deriving Upper Bounds for ${\gamma }_{(k+1)t}^g\left(G\right)$ from ${\gamma }_{kt}^g\left(G\right)$

It is intuitively clear that the greater k is, the more difficult is to find a global total k-dominating set of graph $G=(V,E)$ with the minimum cardinality. In particular, the following relationship is easy to see: ${\gamma }_{1t}^g\left(G\right)\le {\gamma }_{2t}^g\left(G\right)\le {\gamma }_{3t}^g\left(G\right)\le \dots \le {\gamma }_{kt}^g\left(G\right)$, for every $k\le min\{\delta ,n-\Delta -1\}$. Ideally, one would wish to have a method that obtains a GT$(k+1)$D set of minimum cardinality from a GTkD set with the minimum cardinality. It is clear that this is not an easy task. In this next section we develop a method that generates a GT$(k+1)$D set from a GTkD, based on which we establish a relationship between minimum cardinality GTkD and GT$(k+1)$D sets—more precisely, between ${\gamma }_{kt}^g\left(G\right)$ and ${\gamma }_{(k+1)t}^g\left(G\right)$, which, in turn, provides upper bounds for ${\gamma }_{(k+1)t}^g\left(G\right)$.

We first need to introduce some necessary definitions. Given $D\subseteq V$, a subset of the set of vertices V, let $N\left(D\right)$ be the set of vertices from $V\backslash D$ having at least one neighbor in D; that is, $N\left(D\right)=\{x\in V\backslash D$|∃$y\in D$ such that $x\in N_G\left(y\right)\}$. Similarly, we denote by $\overline{N}\left(D\right)$ the set of vertices from $V\backslash D$ having at least one non-neighbor in D.

Now let A and B be subsets of set V. We will say that a subset $D\subseteq A$ is a relative dominating set of B from set A if for every $x\in B$ there exists at least one vertex $v\in D$ such that $v\in N\left(x\right)$ or $v\in B$. Correspondingly, we call the minimum cardinality of such a relative dominating set the relative domination number of set B from set A and denote it by ${\gamma }^{\prime }(A,B)$. We abbreviate by ${\gamma }^{\prime }(A,B)$-set a relative dominating set of B from set A of cardinality ${\gamma }^{\prime }(A,B)$.

Finally, ${\gamma }^{\prime }\left(\overline{A,B}\right)$ is the relative domination number of B from set A in graph $\overline{G}$ and ${\gamma }^{\prime }\left(\overline{A,B}\right)$-set is a relative dominating set of B from set A in graph $\overline{G}$ with cardinality ${\gamma }^{\prime }\left(\overline{A,B}\right)$; see an example in Figure 5.

Lemma 1.

Let G be a graph with diam(G) = 2 and g(G) = 4, and let S be an induced subgraph isomorphic to $C_4$. Let $B=V\backslash \left(N\right(S)\cup S)$ and $A=N\left(B\right)$. Then ${\gamma }_{1t}^g\left(G\right)\le {\gamma }^{\prime }(A,B)+4$.

Proof. 

Let $D^{\prime }$ be a ${\gamma }^{\prime }(A,B)$-set, $D=S\cup D^{\prime }$ and $v\in V$. Note that since $diam\left(G\right)=2$, $D^{\prime }\subseteq A\subseteq N\left(S\right)$. Thus, we can see that $v\in N\left(S\right)$, $v\in B$ or $v\in S$. If $v\in N\left(S\right)$, then it has at least one neighbor in S and hence also in D. On the other hand, if $v\in B$, then v must have at least one neighbor in $D^{\prime }$ and hence also in D. If $v\in S$, then v has at least one neighbor in S, and hence also in D. Therefore, D is a total 1-dominating set of G.

If $v\in S$, then there exists one non-neighbor vertex of v in S, and hence also in D. If $v\in B$, then the four vertices in S are non-neighbors of v, and hence vertex v has at least one non-neighbor in set D. If $v\in N\left(S\right)$, since $g\left(G\right)=4$, v it has at most two neighbors in S; thus, it has at least two non-neighbors in S and hence also in D. Therefore, D is a global 1-dominating set of G. Finally, D is a global total 1-dominating set of G, so ${\gamma }_{1t}^g\left(G\right)\le {\gamma }^{\prime }(A,B)+\left|S\right|={\gamma }^{\prime }(A,B)+4$. □

Corollary 5.

Let G be a graph with diam$\left(G\right)$ = 2 and g$\left(G\right)$ = 4; let S be an induced subgraph isomorphic to $C_4$, $B=V\backslash \left(N\right(S)\cup S)$ and $A=N\left(B\right)$. Then the following conditions hold.

• If $B=\varnothing$, then ${\gamma }_{1t}^g\left(G\right)=4$.
• Since ${\gamma }^{\prime }(A,B)\le \left|B\right|$, ${\gamma }_{1t}^g\left(G\right)\le \left|B\right|+4$.
• If $\left|N\right(x)\cap S|=2$, $\forall x\in A$, then ${\gamma }_{2t}^g\left(G\right)\le 2\left|B\right|+4$.

Let k be a positive integer with $1\le k<min\{\delta ,n-\Delta -1\}$, and D be a ${\gamma }_{kt}^g\left(G\right)$-set for graph G. Below we define special sets of vertices that will be used in future derivations.

• $H=V\left(G\right)\backslash D$.
• $Z=\{x\in H$|${\delta }_D\left(x\right)\ge k+1$ and ${\overline{\delta }}_D\left(x\right)\ge k+1\}$ are all vertices in H which are global total (k + 1)-dominated.
• $X=T_k\left(G\left[D\right]\right)$ are all vertices in D with only k neighbors.
• $Y=T_{\left|D\right|-k-1}\left(G\left[D\right]\right)$ are all vertices in D with only k non-neighbors.
• $X^{\prime }=N\left(X\right)\cap H$ are all the vertices in H which have at least one neighbor in set X.
• $N={\gamma }^{\prime }(X^{\prime },X)$-set, a relative dominating set of X from set $X^{\prime }$.
• $Y^{\prime }=\overline{N}\left(Y\right)\cap H$ are all the vertices in set H which have at least one non-neighbor in set Y.
• $R={\gamma }^{\prime }\left(\overline{Y^{\prime },Y}\right)$-set, a relative dominating set of X from set $X^{\prime }$ in $\overline{G}$.
• $P=H\backslash Z$ are all the vertices in set H which are not yet global total ($k+1$)-dominated.
• $M={\gamma }^{\prime }(H,P)$-set ∪${\gamma }^{\prime }\left(\overline{H,P}\right)$-set;
• $S=D\cup N\cup R\cup M$;

Now we show that the set S obtained as above is a global total $(k+1)$-dominating set given a ${\gamma }_{kt}^g\left(G\right)$-set D.

Theorem 8.

Let G be a graph and D be an arbitrary ${\gamma }_{kt}^g\left(G\right)$-set. Then the set S obtained as above is a global total $(k+1)$-dominating set of graph G.

Proof. 

Let D be an arbitrary ${\gamma }_{kt}^g\left(G\right)$-set, $H=V\backslash D$, $Z=\{x\in H$: ${\delta }_D\left(x\right)\ge k+1$ and ${\overline{\delta }}_D\left(x\right)\ge k+1\}$, $X=T_k\left(G\left[D\right]\right)$ and $Y=T_{\left|D\right|-k-1}\left(G\left[D\right]\right)$. Further, let $P=H\backslash Z$, E be a ${\gamma }^{\prime }(H,P)$-set, F be a ${\gamma }^{\prime }\left(\overline{H,P}\right)$-set and $M=E\cup F$ (all these sets being constructed as above specified). If $X=\varnothing$ and $Y=\varnothing$, then every vertex from $D\cup Z$ has at least $k+1$ adjacent and $k+1$ non-adjacent vertices in set D. Besides, note that every vertex $v\in P$ has at least $k+1$ adjacent and $k+1$ non-adjacent vertices in set $D\cup M$. Additionally, since $V=D\cup Z\cup P$, $D\cup M$ is a global total $(k+1)$-dominating set of graph G.

Assume now that $X\ne \varnothing$ and $Y=\varnothing$, and let $X^{\prime }=N\left(X\right)\cap H$ and N be a ${\gamma }^{\prime }(X^{\prime },X)$-set (notice that by the construction of the set $X^{\prime }$, there always exists the set N). Observe that every vertex from set $D\cup Z$ has at least $k+1$ adjacent and $k+1$ non-adjacent vertices in set $D\cup N$. Besides, every vertex $v\in P$ has at least $k+1$ adjacent and $k+1$ non-adjacent vertices in set $D\cup M$. Since $V=D\cup Z\cup P$, $D\cup N\cup M$ is a global total $(k+1)$-dominating set of G.

The case $X=\varnothing$ and $Y\ne \varnothing$ is analogous to the above case. We obtain that $D\cup R\cup M$ is a global total $(k+1)$-dominating set of G, where $Y^{\prime }=\overline{N}\left(Y\right)\cap H$ and R is a ${\gamma }^{\prime }\left(\overline{Y^{\prime },Y}\right)$-set.

Finally, assume that $X\ne \varnothing$ and $Y\ne \varnothing$. Let $X^{\prime }=N\left(X\right)\cap H$, $Y^{\prime }=\overline{N}\left(Y\right)\cap H$, N be a ${\gamma }^{\prime }(X^{\prime },X)$-set and R be a ${\gamma }^{\prime }\left(\overline{Y^{\prime },Y}\right)$-set. Using a similar arguments as above, we again obtain that S is a global total $(k+1)$-dominating set of graph G. □

In the next proposition we derive an upper bound on the cardinality of the global total $(k+1)$-domination number. In the same lemma, we give a necessary condition when the global total $(k+1)$-domination number is equal to the total $(k+1)$-domination number.

Proposition 8.

Let G be a graph with $\delta \ge k$ and D be a ${\gamma }_{kt}^g\left(G\right)$-set. Then the following conditions hold:

(a) 

${\gamma }_{(k+1)t}^g\left(G\right)\le {\gamma }_{kt}^g\left(G\right)+|N\cup R\cup M|$.

(b) 

If $|N\cup M|>\Delta +k-{\gamma }_{kt}^g\left(G\right)$, then ${\gamma }_{(k+1)t}^g\left(G\right)={\gamma }_{(k+1)t}\left(G\right)$.

Proof. 

(a) By Theorem 8, S is a global total $(k+1)$-dominating set of G; hence, the bound trivially holds.

(b) Recall that $\left|S\right|={\gamma }_{kt}^g\left(G\right)+|N\cup R\cup M|$. Additionally, it is easy to see that $S\backslash R$ is a total $(k+1)$-dominating set of G. In [12] it is proved that if ${\gamma }_{kt}\left(G\right)>\Delta +k$, then ${\gamma }_{kt}^g\left(G\right)={\gamma }_{kt}\left(G\right)$ (see Proposition 2.10). Hence, if $\left|S\right|\ge {\gamma }_{kt}^g\left(G\right)+|N\cup M|\ge {\gamma }_{(k+1)t}\left(G\right)>\Delta +k+1$, then ${\gamma }_{(k+1)t}^g\left(G\right)={\gamma }_{(k+1)t}\left(G\right)$. Hence, if $|N\cup M|>\Delta +k+1-{\gamma }_{kt}^g\left(G\right)$ then ${\gamma }_{(k+1)t}^g\left(G\right)={\gamma }_{(k+1)t}\left(G\right)$. □

Using the definition of the above introduced sets and Theorem 8 and Proposition 8, we can obtain a global total k-domination set for any $k=2,\dots ,\min \{\delta ,n-\Delta -1\}$. As a side-result, we also obtain the corresponding upper bounds to a global total k-domination number. Finally, we note that this procedure provides a global total k-dominating set of minimum cardinality, $2\le k\le min\{\delta ,n-\Delta -1\}$, for some graphs; see Figure 6.

6. Conclusions

We studied the global total k-domination number in general graphs. In particular, we presented new upper and lower bounds using the algebraic connectivity in graphs. We also established a relationship between the global total k-domination numbers of the originally given graph G and the transformed ones. Then we derived an explicit relationship between a ${\gamma }_{kt}^g\left(G\right)$-set and a ${\gamma }_{(k+1)t}^g\left(G\right)$-set, which allowed us to obtain another upper bound for the global total k-domination number in a recurrent fashion, starting from $k=1$. We gave an example of a graph G for which a ${\gamma }_{kt}^g\left(G\right)$-set, for every $k=2,\dots ,\min \{\delta ,n-\Delta -1\}$ is provided. For future work, the global total k-domination number could be studied on unitary operations in graphs, such as edge subdivision, edge contraction, path contraction and removal of a vertex. It would be a challenging task to adopt the proposed method as such and also extend it for a wider class of graphs.