Total Domination on Some Graph Operators

Abstract

Let $G=(V,E)$ be a graph; a set $D\subseteq V$ is a total dominating set if every vertex $v\in V$ has, at least, one neighbor in D. The total domination number ${\gamma }_t\left(G\right)$ is the minimum cardinality among all total dominating sets. Given an arbitrary graph G, we consider some operators on this graph; $\mathtt{S}\left(G\right),\mathtt{R}\left(G\right)$, and $\mathtt{Q}\left(G\right)$, and we give bounds or the exact value of the total domination number of these new graphs using some parameters in the original graph G.

1. Introduction

The study of the mathematical and structural properties of operators in graphs was initiated in Reference [1]. This study is a current research topic, mainly because of its multiple theoretical and practical applications (see References [2,3,4,5,6]). Motivated by the previous investigations, we work here on the total domination number of some graph operators. Other important parameters have also been studied in this type of graphs (see References [7,8]).

We denote by $G=(V,E)$ a finite simple graph of order $n=\left|V\right|$ and size $m=\left|E\right|$. For any two adjacent vertices $u,v\in V$, $uv$ denotes the corresponding edge, and we denote $N\left(v\right)=\{u\in V:uv\in E\}$ and $N\left[v\right]=N\left(v\right)\cup \left\{v\right\}$. We denote by $\Delta$, $\delta$ the maximum and minimum degree, respectively. For a non-empty subset $D\subseteq V$, and any vertex $v\in V$, we denote by $N_D\left(v\right)$ the set of neighbors of v in D, that is, $N_D\left(v\right)=\{u\in D:uv\in E\}$, and $d_D\left(v\right)=\left|N_D\left(v\right)\right|$. The subgraph of G induced by a set of vertices $D\subseteq V$ is denoted by $G\left[D\right]$, and we denote by $G-D$ the graph in which its set of vertices is $V\backslash D$ and in which its set of edges is $\{uv\in E:u,v\in V\backslash D\}$.

A set $D\subseteq V$ is a total dominating set if every vertex $v\in V$ has, at least, a neighbor in D. The total domination number ${\gamma }_t\left(G\right)$ is the minimum cardinality among all total dominating sets. The domination theory has been studied in [9,10,11,12,13,14,15,16], and a generalization of this concept, namely, the total k-domination number, has been studied, for instance, in References [17,18,19,20].

The study of the mathematical properties of the line graph was initiated in 1932 with Whitney’s seminal work [21]. It should be noted that this research has served as a basis for multiple investigations (see, for instance, References [22,23,24]).

For any graph $G=(V,E)$: The line graph of a graph G, denoted by $\mathtt{L}\left(G\right)$, is the graph in which its vertices correspond to the edges of G such that two vertices are adjacent if and only if the corresponding edges in G have a common vertex (see Figure 1).

For any graph $G=(V,E)$: The subdivision operator, denoted by $\mathtt{S}\left(G\right)$, acts on G by replacing each of its edge by a path of length two (see Figure 2).

For any graph $G=(V,E)$: The operator $\mathtt{R}\left(G\right)$ acts on G by adding a new vertex corresponding to each edge of G and by joining each new vertex to the end vertices of the edge corresponding to it (see Figure 3).

Finally, for any graph $G=(V,E)$: The operator $\mathtt{Q}\left(G\right)$ acts on G by inserting a new vertex into each edge of G and by joining every pair of these new vertices which lie on adjacent edges of G (see Figure 4).

In this work, we give bounds and some exact values for the total domination number in these graph operators.

2. Results

2.1. Total Domination Number in the Graph $\mathtt{S}\left(G\right)$

We will use the following notation. If $G=(V,E)$, where $V=\{v_1,\dots ,v_n\}$, then $\mathtt{S}\left(G\right)=(V^{\prime },E^{\prime })$, where $V^{\prime }=V\cup \{v^{i,j}:v_i{v}_j\in E,i<j\}$ and $E^{\prime }=\{v_i{v}^{i,j},v_j{v}^{i,j}:v_i{v}_j\in E,i<j\}$. To avoid writing all the time $i<j$, we will consider $v^{i,j}=v^{j,i}$.

The independence number of a graph G, denoted by $\alpha \left(G\right)$, is the cardinality of the largest independent vertex set in G. A matching in a graph G is a set of edges such that every edge in the set does not have any common vertex with any other edge in the set. A perfect matching is a matching such that every vertex in the graph belongs to an edge in the set.

Theorem 1.

Let G be a graph with order n, then

$$n\le {\gamma }_t\left(\mathtt{S}\left(G\right)\right)\le ⌊\frac{3n-\alpha \left(G\right)}{2}⌋.$$

Proof. 

Let D be a minimum total dominating set in $\mathtt{S}\left(G\right)$. If $v\in V\left(G\right)$ does not belong to D, then $N_G\left(v\right)\subseteq D$, that means, $V\left(G\right)\backslash D$ is an independent set in G. On one hand, since every vertex $v_i\in V\left(G\right)\backslash D$ must be dominated by D, there exists $j\ne i$ such that $v^{i,j}\in D$. Therefore,

$$\left|D\right|\ge \left|V\right(G)\cap D|+\left|V\right(G)\backslash D|=n.$$

If we denote $t=\alpha \left(G\right)$, we will find a total dominating set D in $\mathtt{S}\left(G\right)$ with cardinality $\left|D\right|\le \frac{3n-\alpha \left(G\right)}{2}$. Let $A=\{v_1,v_2,\dots ,v_t\}$ be an independent set in G, and we take $V\left(G\right)\backslash A\subseteq D$. Let $M_1=\{v_1{v}_{t+1},v_2{v}_{t+2},\dots ,v_r{v}_{t+r}\}$ be the biggest matching we can get in the graph with one vertex of each edge in A. Consider the sets $M_1^{\prime }=\{v^{i,t+i}:v_i{v}_{t+i}\in M_1\}$ and $N_1^{\prime }=\{v^{r+1,t+l_1},v^{r+2,t+l_2},\dots ,$$v^{t,t+l_{t-r}}:v_{r+k}{v}_{t+l_k}\in E\left(G\right)\}$.

Now, we consider the biggest matching using vertices in $\{v_{t+r+1},v_{t+r+2},\dots ,v_n\}$, which we suppose is $M_2=\{v_{t+r+1}{v}_{t+r+2},v_{t+r+3}{v}_{t+r+4},\dots ,v_{t+r+2p-1}{v}_{t+r+2p}\}$, and consider the set $M_2^{\prime }=\{v^{t+r+i,t+r+i+1}:v_{t+r+i}{v}_{t+r+i+1}\in M_2\}$. The set $\{v_{t+r+2p+1},$$\dots ,v_{t+r+2p+s}\}$, with $s=n-(t+r+2p)$, is an independent set and it does not have any connection with vertices in $\{v_{r+1},v_{r+2},\dots ,v_t\}$ (since otherwise there would be at least one edge $v_{k_1}{v}_{k_2}\in M_1$, for some $r<k_1\le t$ and $t+r+2p<k_2\le n$, which contradicts the maximality of $M_1$). Consider the set $N_2^{\prime }=\{v^{t+r+2p+1,i_1},v^{t+r+2p+2,i_2}$$,\dots ,$ $v^{t+r+2p+s,i_s}:v_{t+r+2p+j}{v}_{i_j}\in E\left(G\right)\}$.

In this case, we can take $D=(V\left(G\right)\backslash A)\cup M_1^{\prime }\cup M_2^{\prime }\cup N_1^{\prime }\cup N_2^{\prime }$.

Notice that D is a total dominating set in $\mathtt{S}\left(G\right)$ and, since $s+t-r\le t$ because of the maximality of A, its cardinality satisfies

$$\begin{array}{ccc}\hfill \left|D\right|& =& (n-t)+r+p+(t-r)+s=n+p+s\le n+\frac{r+2p+s}{2}\hfill \\ & =& n+\frac{n-t}{2}=\frac{3n-t}{2}.\hfill \end{array}$$

□

The lower bound given in Theorem 1 is attained in any tree (see Reference [14]) and cycles with order $n\ne 4k+1$, and the upper bound is attained when G is a star or a complete graph.

The following corollary might be useful when we do not know the independence number.

Corollary 1.

Let G be a graph with order n, which is not a complete graph, then

$${\gamma }_t\left(\mathtt{S}\left(G\right)\right)\le ⌊\frac{3n}{2}⌋-1.$$

It is known (see Reference [13]) that

$${\gamma }_t\left(P_n\right)={\gamma }_t\left(C_n\right)=\left\{\begin{array}{cc}\frac{n}{2}+1& \mathrm{if}n\equiv 2\left(\mathrm{mod}4\right)\hfill \\ ⌈\frac{n}{2}⌉& \mathrm{otherwise}.\hfill \end{array}\right.$$

Since $\mathtt{S}\left(C_n\right)=C_{2n}$, the total domination number of the transformation of this graph is ${\gamma }_t\left(\mathtt{S}\left(C_n\right)\right)=n+1$ when $n\equiv 1$ (mod 2) [if $n\equiv 3$ (mod 4), then $2n=2$ (mod 4)], and ${\gamma }_t\left(\mathtt{S}\left(C_n\right)\right)=n$ otherwise.

Proposition 1.

For a wheel $W_n$ with n vertices, we have

$${\gamma }_t\left(\mathtt{S}\left(W_n\right)\right)=2+{\gamma }_t\left(P_{2n-3}\right).$$

Proof. 

Let $V\left(W_n\right)=\{v_1,v_2,\dots ,v_n\}$, where $v_1$ is the center of the wheel. If $D_0$ is a minimum total dominating set in the path with vertices $v^{2,3},v_3,v^{3,4},v_4,\dots ,$$v_n,v^{n,2}$, then $D=\{v_1,v^{1,2}\}\cup D_0$ is a total dominating set in $\mathtt{S}\left(W_n\right)$, so

$${\gamma }_t\left(\mathtt{S}\left(W_n\right)\right)\le 2+{\gamma }_t\left(P_{2n-3}\right).$$

Let D be a minimum total dominating set in $\mathtt{S}\left(W_n\right)$ such that $v_1,v^{1,2}\in D$. Since this set must contain a total dominating set in the path in which its vertices are $v^{2,3}$, $v_3$, $v^{3,4}$, $v_4$, …, $v_n$, $v^{n,2}$, then $\left|D\right|\ge 2+{\gamma }_t\left(P_{2n-3}\right)$. If $v_1$ does not belong to a total dominating set $D^{\prime }$, then $v_2,v_3,v_4,\dots ,v_n$ must belong to $D^{\prime }$. Moreover, as $\{v_2,v_3,v_4,\dots ,v_n\}$ is an independent set, we need $⌈\frac{n-1}{2}⌉$ more vertices, and then $|D^{\prime }|>2+{\gamma }_t\left(P_{2n-3}\right).$ □

Proposition 2.

For the complete graph $K_n$, we have

$${\gamma }_t\left(\mathtt{S}\left(K_n\right)\right)=⌈\frac{3n}{2}⌉-1.$$

Proof. 

We denote $V\left(K_n\right)=\{v_1,\dots ,v_n\}$. First at all, if n is an even number, the set $\{v^{1,2},v_2,v_3,v^{3,4},v_4,\dots ,v_{n-1},v^{n-1,n},v_n\}$ is a total dominating set, and, if n is an odd number, the set $\{v^{1,2},v_2,v_3,v^{3,4},v_4,\dots ,v_{n-2},v^{n-2,n-1},v_{n-1},v_n,$$v^{1,n}\}$ is a total dominating set. Then,

$${\gamma }_t\left(\mathtt{S}\left(K_n\right)\right)\le ⌈\frac{3n}{2}⌉-1.$$

Now, let D be a minimum total dominating set in $\mathtt{S}\left(K_n\right)$. If there exists $v_i\notin D$, then, to dominate $v^{s,i}$ with $s\ne i$, it is necessary to have $v_s\in D$ for every $s\ne i$. As $v_i$ must be dominated by D, there exists $j\ne i$ such that $v^{i,j}\in D$. Since $v_s\in D$ for every $s\ne i$, and it is an independent set in $\mathtt{S}\left(K_n\right)$, for every two of those vertices, we need another vertex in D connecting them. Therefore, $\left|D\right|\ge n+\frac{n-2}{2}=\frac{3n}{2}-1$. Finally, if $\{v_1,\dots ,v_n\}\subseteq D$, since that is an independent set in $\mathtt{S}\left(K_n\right)$, D must contain, at least, $\frac{n}{2}$ more vertices, so $\left|D\right|\ge n+\frac{n}{2}\ge ⌈\frac{3n}{2}⌉-1.$ □

2.2. Total Domination Number of $\mathtt{R}\left(G\right)$

We will use the following notation. If $G=(V,E)$, where $V=\{v_1,\dots ,v_n\}$, then $\mathtt{R}\left(G\right)=(V^{\prime },E^{\prime })$, where $V^{\prime }=V\cup \{v^{i,j}:v_i{v}_j\in E\}$ and $E^{\prime }=E\cup \{v_i{v}^{i,j},v_j{v}^{i,j}:v_i{v}_j\in E\}$ (we will consider $v^{i,j}=v^{j,i}$).

A total dominating set D of a graph G is called a total co-independent dominating set if the set of vertices $V\backslash D$ is a non-empty independent set. The minimum cardinality of any total co-independent dominating set is the total co-independent domination number, and it is denoted by ${\gamma }_{t,coi}\left(G\right)$.

Theorem 2.

For any graph G with order $n\ge 3$, we have

$${\gamma }_t\left(\mathtt{R}\left(G\right)\right)={\gamma }_{t,coi}\left(G\right).$$

Proof. 

If D is a total co-independent dominating set in G, it is a total dominating set in G and any edge contains a vertex of D, and then it is a total dominating set in $\mathtt{R}\left(G\right)$. Therefore,

$${\gamma }_t\left(\mathtt{R}\left(G\right)\right)\le {\gamma }_{t,coi}\left(G\right).$$

Now, let D be a minimum total dominating set in $\mathtt{R}\left(G\right)$. If $v^{i,j}\in D$ for some $1\le i<j\le n$, then we have that $v_i\in D$ or $v_j\in D$. If, for instance, $v_i\in D$, we can take $D^{\prime }=(D\backslash \left\{v^{i,j}\right\})\cup \left\{v_j\right\}$, which is also a minimum total dominating set in $\mathtt{R}\left(G\right)$. Doing that with any vertex $v^{i,j}\in D$, we obtain a total dominating set $D^{\prime }\subseteq V$ in both graphs $\mathtt{R}\left(G\right)$ and G such that any edge in E contains a vertex of $D^{\prime }$, so $D^{\prime }$ is a total co-independent dominating set of G. Therefore,

$${\gamma }_{t,coi}\left(G\right)\le |D^{\prime }| =|D|={\gamma }_t\left(\mathtt{R}\left(G\right)\right).$$

□

The following two results are directly obtained from References [15,16].

Proposition 3.

Let G be a graph with order n and independence number $\alpha \left(G\right)$. Then,

$$n-\alpha \left(G\right)\le {\gamma }_t\left(\mathtt{R}\left(G\right)\right)\le 2(n-\alpha \left(G\right)).$$

Proposition 4.

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

$$max\left\{\frac{n\delta }{\Delta +\delta -1},\frac{2m+n\delta }{3\Delta +\delta -2}\right\} \le {\gamma }_t\left(\mathtt{R}\left(G\right)\right)\le n-1.$$

Moreover, ${\gamma }_t\left(\mathtt{R}\left(G\right)\right)=n-1$ if and only if G is $K_n$, $P_3,C_4$, or $C_5$.

Let us show new upper bounds giving some conditions on the graph. A leaf in a graph $G=(V,E)$ is a vertex $v\in V$ such that $d\left(v\right)=1$. A support vertex in G is a non-leaf vertex adjacent to a leaf. A hair in G is an edge $uv\in E$ such that $d\left(u\right)=2$ and $d\left(v\right)=1$.

Proposition 5.

If $l\left(G\right)$ is the number of leaves of a graph G with order n, and there exists a vertex v, such that it is not a leaf, nor a support vertex, nor adjacent to any hair, then

$${\gamma }_t\left(\mathtt{R}\left(G\right)\right)\le n-l\left(G\right)-1.$$

Proof. 

If $L=\{u\in V:d(u)=1\}$, then the set $D=V\backslash (L\cup \{v\left\}\right)$ is a total dominating set in G. Since v is neither a support vertex nor adjacent to any hair, and $L\cup \left\{v\right\}$ is an independent set, we have that D is a total co-independent dominating set in G. Therefore,

$${\gamma }_t\left(\mathtt{R}\left(G\right)\right)\le \left|D\right|=n-l\left(G\right)-1.$$

□

The upper bound in Proposition 5 is attained, for instance, if we take any graph G with minimum degree $\delta \ge 2$, and we add a leaf to every vertex in G except one.

Proposition 6.

Let G be a graph with order n, minimum degree $\delta \ge 2$ and independence number $\alpha \left(G\right)$. Then, ${\gamma }_t\left(\mathtt{R}\left(G\right)\right)\le n-\delta +1$ if and only if $\alpha \left(G\right)\ge \delta -1$.

Proof. 

On one hand, if $\alpha \left(G\right)\ge \delta -1$, and we take an independent set $A=\{v_1,v_2,\dots ,v_{\delta -1}\}$, every vertex $v\in V\backslash A$ satisfies $d_{V\backslash A}\left(v\right)\ge 1$, and then $V\backslash A$ is a total co-independent dominating set in G, so ${\gamma }_t\left(\mathtt{R}\left(G\right)\right)\le n-\delta +1$.

On the other hand, if $\alpha \left(G\right)\le \delta -2$, by Proposition 3, we have

$${\gamma }_t\left(\mathtt{R}\left(G\right)\right)\ge n-\alpha \left(G\right)\ge n-\delta +2.$$

□

Corollary 2.

Let G be a graph with order n, minimum degree $\delta \ge 2$, and independence number $\alpha \left(G\right)$. The following conditions hold:

(1)

if $\alpha \left(G\right)=\delta -1$, then ${\gamma }_t\left(\mathtt{R}\left(G\right)\right)=n-\alpha \left(G\right)$.

(2)

if $\alpha \left(G\right)\ge \delta$, then ${\gamma }_t\left(\mathtt{R}\left(G\right)\right)\le n-\delta +1$.

Theorem 3.

Let G be a graph with order n, minimum degree δ, and maximum degree Δ. If $n\ge (\delta -3)\Delta +\delta +2$, then

$${\gamma }_t\left(\mathtt{R}\left(G\right)\right)\le n-\delta +1.$$

Proof. 

Let $v_1$ be any vertex in the graph such that $\delta \left(v_1\right)=\delta$, and we take any vertex $v_2\in V\backslash \left\{v_1\right\}$ adjacent to $N\left(v_1\right)$. Note that $\{v_1,v_2\}$ is an independent set, and $|N\left[v_1\right]\cup N\left[v_2\right]|\le \delta +1+\Delta$.

Now, since G is a connected graph, there exists $v_3\in V\backslash \{v_1,v_2\}$ adjacent to $N\left(v_1\right)\cup N\left(v_2\right)$, and then we have that $\{v_1,v_2,v_3\}$ is an independent set, and $|N\left[v_1\right]\cup N\left[v_2\right]\cup N\left[v_3\right]|\le \delta +1+2\Delta$.

We can continue this process to obtain an independent set $A=\{v_1,v_2,\dots ,v_{\delta -1}\}$.

Using Corollary 2, we conclude that

$${\gamma }_t\left(\mathtt{R}\left(G\right)\right)\le n-\delta +1.$$

□

The upper bound given in Theorem 3 is attained, for instance, if we consider a complete graph $G_1$ with 5 vertices $v_1,\dots ,v_5$, a ($2r-2$)-regular graph $G_2$ with vertices $u_1,u_2,\dots ,u_{2r}$ ($r\ge 3$), and the graph $G=(V,E)$ with order $n=2r+5$ such that $V=V\left(G_1\right)\cup V\left(G_2\right)$ and $E=E\left(G_1\right)\cup E\left(G_2\right)\cup \{v_1{u}_1,v_2{u}_2\}$. In such a case, $\alpha \left(G\right)=3$, $\delta \left(G\right)=4$, $\Delta \left(G\right)=2r-1$, $n=\left(\delta \right(G)-3)\Delta \left(G\right)+\delta \left(G\right)+2$, and ${\gamma }_t\left(\mathtt{R}\left(G\right)\right)=n-\delta \left(G\right)+1$.

Using the results shown in Reference [16], we know that, for the cycle $C_n$, the wheel $W_n$, and the complete graph $K_n$ with n vertices, we have

$${\gamma }_t\left(\mathtt{R}\left(C_n\right)\right)=⌈\frac{2n}{3}⌉,$$

$${\gamma }_t\left(\mathtt{R}\left(W_n\right)\right)=⌈\frac{n+1}{2}⌉,$$

$${\gamma }_t\left(\mathtt{R}\left(K_n\right)\right)=n-1.$$

2.3. Total Domination Number of $\mathtt{Q}\left(G\right)$

We will use the following notation. If $G=(V,E)$, where $V=\{v_1,\dots ,v_n\}$, then $\mathtt{Q}\left(G\right)=(V^{\prime },E^{\prime })$, where $V^{\prime }=V\cup \{v^{i,j}:v_i{v}_j\in E\}$ and $E^{\prime }=\{v_i{v}^{i,j},v_j{v}^{i,j}:v_i{v}_j\in E\}\cup \{v^{i,j}{v}^{j,k}:v_i{v}_j,v_j{v}_k\in E\}$ (we will consider $v^{i,j}=v^{j,i}$). The line graph $\mathtt{L}\left(G\right)$ is the graph in which its set of vertices is $\{v^{i,j}:v_i{v}_j\in E\}$ and in which its set of edges is $\{v^{i,j}{v}^{j,k}:v_i{v}_j,v_j{v}_k\in E\}$.

A set $D\subseteq V$ is a k-tuple dominating set if every vertex $v\in V$ satisfies $\left|N\right[v]\cap D|\ge k$. The k-tuple domination number ${\gamma }_{\times k}\left(G\right)$ is the minimum cardinality among all k-tuple dominating sets. For more information about this parameter, see, for instance, References [19,20].

Proposition 7.

For any graph G, there exists a minimum total dominating set D in $\mathtt{Q}\left(G\right)$ such that all its vertices belong to $V\left(\mathtt{L}\right(G\left)\right)$. Moreover, this set is 2-tuple dominating set in $\mathtt{L}\left(G\right)$.

Proof. 

We know that $V\left(\mathtt{Q}\right(G\left)\right)=V\left(G\right)\cup V\left(\mathtt{L}\right(G\left)\right)$. Let D be a minimum total dominating set in $\mathtt{Q}\left(G\right)$, and we suppose $v_i\in D$. We denote $N_G\left(v_i\right)=\{v_{i_1},\dots ,v_{i_r}\}$. If $r=1$, then $v^{i,i_1}\in D$. Taking any neighbor $v_j$ of $v_{i_1}$, we have that $D^{\prime }=(D\backslash \left\{v_i\right\})\cup \left\{v^{i_1,j}\right\}$ is a total dominating set in $\mathtt{Q}\left(G\right)$.

If $r\ge 2$, and we suppose that $v^{i,i_1}\in D$, the set $D^{\prime }=(D\backslash \left\{v_i\right\})\cup \left\{v^{i,i_2}\right\}$ is a total dominating set in $\mathtt{Q}\left(G\right)$. Moreover, if $v^{r,s}\notin D^{\prime }$ for some $r\ne s$, since $v_r$ and $v_s$ must be dominated by $D^{\prime }$, there exists $v_l$ and $v_t$ adjacent to $v_r$ and $v_s$, respectively, such that $v^{r,l},v^{s,t}\in D^{\prime }$, and then every vertex in $V\left(\mathtt{L}\left(G\right)\right)\backslash D^{\prime }$ is dominated by two vertices in $D^{\prime }$. □

Corollary 3.

For any graph G with size m,

$${\gamma }_{\times 2}\left(\mathtt{L}\left(G\right)\right)\le {\gamma }_t\left(\mathtt{Q}\left(G\right)\right)\le m.$$

It can be checked that ${\gamma }_{\times 2}\left(\mathtt{L}\left(P_n\right)\right)={\gamma }_t\left(\mathtt{Q}\left(P_n\right)\right)$ for any path $P_n$ with n vertices, but there are infinitely many graphs such that ${\gamma }_{\times 2}\left(\mathtt{L}\left(G\right)\right)<{\gamma }_t\left(\mathtt{Q}\left(G\right)\right)$. For instance, if we take k paths with five consecutive vertices $v_1^i,v_2^i,v_3^i,v_4^i,v_5^i$, for $i\in \{1,\dots ,k\}$, j extra vertices $u_1,u_2,\dots ,u_j$ and the edges $u_s{v}_3^i$ for every $i\in \{1,\dots ,k\}$ and $s\in \{1,\dots ,j\}$, the graph G obtained satisfies ${\gamma }_{\times 2}\left(\mathtt{L}\left(G\right)\right)+j={\gamma }_t\left(\mathtt{Q}\left(G\right)\right)$. We obtain the same if we change any path with five vertices by a cycle with three vertices.

Given a graph G, we denote by $p_3\left(G\right)$ the maximum number of independent paths with three vertices we can get in G, that is, without vertices in common.

Theorem 4.

Let G be a graph with order n. Then,

$${\gamma }_t\left(\mathtt{Q}\left(G\right)\right)=n-p_3\left(G\right).$$

Proof. 

Let $p_3\left(G\right)=r$, and let $\{v_1,v_2,v_3\},\{v_4,v_5,v_6\},\dots ,\{v_{3r-2},v_{3r-1},v_{3r}\}$ be the corresponding sets of vertices of the independent paths. We will choose a total dominating set D in $\mathtt{Q}\left(G\right)$ such that $\left|D\right|\le n-p_3\left(G\right)$. We take $v^{1,2},v^{2,3},v^{4,5},v^{5,6},\dots ,v^{3r-2,3r-1},v^{3r-1,3r}$ in D. Now, if we have an edge $v_i{v}_j$ with $i,j>3r$, there exists $k_i\in \{1,2,\dots ,3r\}$ such that $v_i{v}_{k_i}\in E$, or there exists $k_j\in \{1,2,\dots ,3r\}$ such that $v_j{v}_{k_j}\in E$. Then, we take $v^{k_i,i},v^{i,j}$ or $v^{k_j,j},v^{i,j}$ in D.

Finally, if $i>3r$ and $v_i{v}_j\notin E$ for any $j>3r$, there exists $k_i\in \{1,2,\dots ,3r\}$ such that $v_i{v}_{k_i}\in E$, and then we take $v^{k_i,i}$ in D. It can be checked that D is a total dominating set with cardinality $2r+n-3r=n-r$. Consequently,

$${\gamma }_t\left(\mathtt{Q}\left(G\right)\right)\le n-p_3\left(G\right).$$

Now, we will prove that ${\gamma }_t\left(\mathtt{Q}\left(G\right)\right)\ge n-p_3\left(G\right)$ by induction in the number of vertices. If G is a connected graph with order $n\in \{3,4\}$, it is clear that $p_3\left(G\right)=1$ and ${\gamma }_t\left(\mathtt{Q}\left(G\right)\right)=n-1$. Then, we suppose that the inequality is true for any graph with order smaller than n, and let us prove the inequality for any graph with n vertices. We consider a graph G with n vertices and, by Proposition 7, a minimum total dominating set D in $\mathtt{Q}\left(G\right)$ such that $D\subseteq V\left(\mathtt{L}\right(G\left)\right)$.

We suppose that $v^{1,2},v^{2,3}\in D$, then, if $v_1{v}_3\in E$, we have that $v^{1,3}\notin D$.

Claim 1. If there exists three vertices $v_j,v_{j+1},v_{j+2}\in V\left(G\right)$ such that $v_i{v}_j,$$v_j{v}_{j+1},v_{j+1}{v}_{j+2}\in E\left(G\right)$ and $v^{i,j}\in D$ for some $i\in \{1,2,3\}$ and $4\le j\le n-2$, then there exists another minimum total dominating set $D^{\prime }\subseteq V\left(\mathtt{L}\left(G\right)\right)$ such that $v^{1,2},v^{2,3}\in D^{\prime }$ but $v^{i,j}\notin D^{\prime }$.

Proof of Claim 1. Without loss of generality, we suppose that $i=3$ and $j=4$. If there exist two vertices $v_t,v_r\in (V\left(G\right)\cap (N\left(v_4\right)\backslash \left\{v_3\right\}))$ such that $v^{4,t},v^{4,r}\in D$, then $D^{\prime }=D\backslash \left\{v^{3,4}\right\}$ is a total dominating set in $\mathtt{Q}\left(G\right)$, a contradiction. If there exists $v_t\in (V\left(G\right)\cap (N\left(v_4\right)\backslash \left\{v_3\right\}))$ such that $v^{4,t}\notin D$, then $D^{\prime }=(D\backslash \left\{v^{3,4}\right\})\cup \left\{v^{4,t}\right\}$ is a total dominating set in $\mathtt{Q}\left(G\right)$. Therefore, we suppose that ${\delta }_G\left(v_4\right)=2$ and $v^{4,5}\in D$. If there exists $v_t\in (V\left(G\right)\cap (N\left(v_5\right)\backslash \left\{v_4\right\}))$ such that $v^{5,t}\in D$, then $D^{\prime }=D\backslash \left\{v^{3,4}\right\}$ is a total dominating set in $\mathtt{Q}\left(G\right)$, a contradiction.

Consequently, $D^{\prime }=(D\backslash \left\{v^{3,4}\right\})\cup \left\{v^{5,6}\right\}$ is a total dominating set in $\mathtt{Q}\left(G\right)$ with the same cardinality.

Let us observe that

$$G-\{v_1,v_2,v_3\}=G_1^{\prime }\cup \cdots \cup G_r^{\prime }\cup G_{r+1}^{″}\cup \cdots \cup G_{r+s}^{″}\cup G_{r+s+1}^{‴}\cup \cdots \cup G_{r+s+t}^{‴},$$

where $G_i^{\prime },G_i^{″},G_i^{‴}$ are connected graphs with orders 1,2 or more than 3, respectively. If we denote by $H_3=G_{r+s+1}^{‴}\cup \cdots \cup G_{r+s+t}^{‴}$ and $H=G-V\left(H_3\right)$, by Claim 1, we can suppose that $D=(D\cap V\left(\mathtt{Q}\left(H\right)\right))\cup (D\cap V\left(\mathtt{Q}\left(H_3\right)\right))$.

Claim 2.$|D\cap V(\mathtt{Q}\left(H\right)\left)\right|=n\left(H\right)-1$.

Proof of Claim 2. Since H is a graph with a path with three vertices, isolated vertices connected to this path, isolated segments connected to this path, and we have two vertices of D to dominate this path, we know that D needs to have one more vertex for any isolate vertex and two more vertices for any isolated segment, so $|D\cap V(\mathtt{Q}\left(H\right)\left)\right|=n\left(H\right)-1$.

Finally, since $D\cap V\left(\mathtt{Q}\left(H_3\right)\right)$ is a total dominating set in $\mathtt{Q}\left(H_3\right)$, by induction, we have

$$\begin{array}{ccc}\hfill \left|D\right|& =& |D\cap V\left(\mathtt{Q}\left(H\right)\right)|+|D\cap V\left(\mathtt{Q}\left(H_3\right)\right)|\ge n\left(H\right)-1+{\gamma }_t\left(\mathtt{Q}\left(H_3\right)\right)\hfill \\ & \ge & n\left(H\right)-1+n\left(H_3\right)-p_3\left(H_3\right)=n-(p_3\left(H_3\right)+1)\ge n-p_3\left(G\right).\hfill \end{array}$$

□

Corollary 4.

Let G be a graph of order n. Then,

$$⌈\frac{2n}{3}⌉\le {\gamma }_t\left(\mathtt{Q}\left(G\right)\right)\le n-1.$$

A Hamiltonian path in a graph is a path that visits every vertex of the graph exactly once.

Proposition 8.

If G is a graph with order n, and it has a Hamiltonian path, then

$${\gamma }_t\left(\mathtt{Q}\left(G\right)\right)=⌈\frac{2n}{3}⌉.$$

Corollary 5.

For the cycle $C_n$, the wheel $W_n$, and the complete graph $K_n$ with n vertices, we have

$${\gamma }_t\left(\mathtt{Q}\left(C_n\right)\right)={\gamma }_t\left(\mathtt{Q}\left(W_n\right)\right)={\gamma }_t\left(\mathtt{Q}\left(K_n\right)\right)=⌈\frac{2n}{3}⌉.$$

Remark 1.

There is not a general inequality for ${\gamma }_t\left(\mathtt{R}\left(G\right)\right)$ and ${\gamma }_t\left(\mathtt{Q}\left(G\right)\right)$. For instance, for the star graph $S_n$ with n vertices and the complete graph $K_n$, we have

$${\gamma }_t\left(\mathtt{R}\left(S_n\right)\right)=2<n-1={\gamma }_t\left(\mathtt{Q}\left(S_n\right)\right),$$

and

$${\gamma }_t\left(\mathtt{Q}\left(K_n\right)\right)=⌈\frac{2n}{3}⌉<n-1={\gamma }_t\left(\mathtt{R}\left(K_n\right)\right).$$

3. Conclusions

Domination theory in graphs has been consolidated as an important area of study within Discrete Mathematics, due to its multiple theoretical and applied applications. This research opens a door to analyze the properties of the different parameters associated to the Domination Theory in the studied unitary operators ($\mathtt{S}\left(G\right)$, $\mathtt{R}\left(G\right)$, and $\mathtt{Q}\left(G\right)$).

It should be noted that the mathematical properties of some parameters associated with the Domination Theory (number of alliances, domination number, total domination number, etc.) have been studied essentially on two unitary operators (named line and complement). In the above direction, this research continues with the study of an important parameter of the Domination Theory (total domination number) when unitary operators ($\mathtt{S}\left(G\right)$, $\mathtt{R}\left(G\right)$, and $\mathtt{Q}\left(G\right)$) act on graphs. In particular, we find optimal bounds, and, in some cases, we give closed formulas for the number of total domination when certain operators act on the graph.