Farshad Kazemnejad^a , Behnaz Pahlavsay^b , Elisa Palezzato^b , Michele Torielli^∗c

^aFaculty of Basic Sciences, Department of Mathematics, Ilam University, P.O.Box 69315-516, Ilam, Iran ^bDepartment of Mathematics, Hokkaido University, Kita 10, Nishi 8, Kita-Ku, Sapporo 060-0810, Japan ^cDepartment of Mathematics, GI-CoRE GSB, Hokkaido University, Kita 10, Nishi 8, Kita-Ku, Sapporo 060-0810, Japan

kazemnejad.farshad@gmail.com, pahlavsayb@gmail.com, palezzato@math.sci.hokudai.ac.jp, torielli@math.sci.hokudai.ac.jp

A total dominating set of a graph G with no isolated vertices is a subset S of the vertex set such that every vertex of G is adjacent to a vertex in S. The total domination number of G is the minimum cardinality of a total dominating set of G. In this paper, we study the total domination number of middle graphs. Indeed, we obtain tight bounds for this number in terms of the order of the graph G. We also compute the total domination number of the middle graph of some known families of graphs explicitly. Moreover, some Nordhaus-Gaddum-like relations are presented for the total domination number of middle graphs.

Keywords: total domination number, middle graph, Nordhaus-Gaddum-like relation

Mathematics Subject Classification: 05C69

DOI: 10.5614/ejgta.2022.10.1.19

1. Introduction

The concept of total domination in graph theory was first introduced by Cockayne, Dawes and Hedetniemi in [3] and it has been studied extensively by many researchers in the last years, see for example [5], [6], [7], [13], [8], [10], [12] and [14]. The literature on this subject has been surveyed and detailed in the recent book [7]. We refer to [2] as a general reference on graph theory.

Received: 30 September 2020, Revised: 6 April 2022, Accepted: 11 April 2022.

^∗ corresponding author

Let G be a graph with vertex set V (G) of order n and edge set E(G) of size m. The open neighborhood and the closed neighborhood of a vertex v ∈ V (G) are NG(v) = {u ∈ V (G) | uv ∈ E(G)} and NG[v] = NG(v) ∪ {v}, respectively. For a connected graph G, the degree of a vertex v is dG(v) = |NG(v)|. The distance dG(v, w) in G of two vertices v, w ∈ V (G) is the length of the shortest path connecting the two vertices. The diameter diam(G) of G is the shortest distance between any two vertices in G.

A dominating set of a graph G is a set S ⊆ V (G) such that NG[v] ∩ S 6= ∅, for any vertex v ∈ V (G). The domination number of G is the minimum cardinality of a dominating set of G and is denoted by γ(G).

Definition 1.1. Let G be a graph with no isolated vertices. A total dominating set of G is a set S ⊆ V (G) such that NG(v) ∩ S 6= ∅, for any vertex v ∈ V (G). The total domination number of G is the minimum cardinality of a total dominating set of G and is denoted by γt(G).

Example 1.2. Consider the path P³ with vertex set {v1, v2, v3} and edge set {v1v2, v2v3}. Then the set S = {v1, v2} is a total dominating set of P3.

For any non-empty S ⊆ V (G), we denote by G[S] the subgraph of G induced on S. For any v ∈ V (G), we denote by G \ v the subgraph of G induced on V (G) \ {v}.

The complement G of G is a graph with vertex set V (G) such that for every two vertices v and w, vw ∈ E(G) if and only if vw 6∈ E(G).

The line graph of G, denoted by L(G), is the graph with vertex set E(G), where vertices x and y are adjacent in L(G) if and only if edges x and y share a common vertex in G.

In [4], the authors introduced the notion of the middle graph M(G) of G as an intersection graph on V (G).

Definition 1.3. The middle graph M(G) of a graph G = (V, E) is the graph whose vertex set is V (G) ∪ E(G) and two vertices x, y in the vertex set of M(G) are adjacent in M(G) in case one the following holds:

• 1. x, y are in E(G) and x, y are adjacent in G.
• 2. x is in V (G), y is in E(G), and x, y are incident in G.

Example 1.4. Consider the graph P3, then the middle graph M(P3) is the one in Figure 1.

Figure 1. The middle graph M(P3).

It is easy to see that M(G) contains the line graph L(G) as induced subgraph, and that if G is a graph of order n and size m, then M(G) has order n + m and size 2m + |E(L(G))|, and it is obtained by subdividing each edge of G exactly once and joining all the adjacent edges of G in M(G).

In order to avoid confusion, we fix a "standard" notation for V (M(G)) and E(M(G)). Fix V (G) = {v1, v2, . . . , vn}, then V (M(G)) = V (G) ∪ M, where M = {mij | viv^j ∈ E(G)} and E(M(G)) = {vimij , vjmij | viv^j ∈ E(G)} ∪ E(L(G)).

In this article, we continue our study from [9] on domination of middle graphs. The paper proceeds as follows. In Section 2, we describe explicitly the total domination number of the middle graph of several known families of graphs and some upper and lower bounds for γt(M(G)) in terms of the order of G. In Section 3, we describe bounds for the total domination number of the middle graph of trees. In Section 4, we obtain the same type of results for γt(M(G ◦ K1)), γt(M(G ◦ P2)) and γt(M(G+ Kp)). We conclude the paper discussing some Nordhaus-Gaddum like relations for the total domination number of middle graphs.

2. Middle graph of known graphs and their total domination number

We start our study on total domination with two easy Lemmas.

Lemma 2.1. Let G be a connected graph of order n ≥ 3 and S a total dominating set of M(G). Then there exists S ⁰ ⊆ E(G) a total dominating set of M(G) with |S 0 | ≤ |S|.

Proof. If S ⊆ E(G), then take S ⁰ = S. We can then assume that there exists v ∈ S ∩ V (G). If all edges adjacent to v are already in S, then take S¹ = S \ {v}. Otherwise, let e ∈ E(G) \ S be an edge adjacent to v, and consider S¹ = (S ∪ {e}) \ {v}. Since S is a finite set, then this process must terminate after a finite number of steps, and hence we obtain the described S 0 .

Lemma 2.2. Let G be a connected graph of order n ≥ 2 and v ∈ V (G) a vertex not adjacent to any vertex of degree 1. Then

\[\gamma_t(M(G \setminus v)) \le \gamma_t(M(G)) \le \gamma_t(M(G \setminus v)) + 1.\]

Proof. Let S be a total dominating set of M(G\v). This implies that for every w ∈ NG(v), w ∈ S or there exists an edge of the form ww⁰ ∈ E(G\v) such that ww⁰ ∈ S. As a consequence, S∪{vw} is a total dominating set of M(G), for any w ∈ NG(v), and hence γt(M(G)) ≤ γt(M(G \ v)) + 1.

On the other hand, let S be a minimal total dominating set of M(G). By Lemma 2.1, we can assume that S ⊆ E(G). Consider S^v = NM(G)(v) ∩ S. Since S is a minimal total dominating set, |Sv| ≥ 1. Assume S^v = {e1, . . . , ek}. For any 1 ≤ i ≤ k, eⁱ is an edge of G of the form wiv. By the assumption on v, NM(G)(w1) = {e1, e11, . . . , e1p} with p ≥ 1, for some e1^j ∈ E(G \ v). If S ∩ {e11, . . . , e1p} 6= ∅, then consider S¹ = (S \ e1) ∪ {w1}, otherwise S¹ = (S \ e1) ∪ {e11}. By applying the same construction for each eⁱ , we obtain S^k a total dominating set of M(G \ v) with |Sk| = |S|, and hence γt(M(G \ v)) ≤ γt(M(G)).

We are now ready to describe explicitly the total dominating number of the middle graph of several known families of graphs.

Proposition 2.3. For any star graph K1,n on n + 1 vertices, with n ≥ 2, we have

\[\gamma_t(M(K_{1,n})) = n.\]

Proof. Fix \(V(K_{1,n}) = \{v_0, v_1, \dots, v_n\}\) and \(E(K_{1,n}) = \{v_0v_1, v_0v_2, \dots, v_0v_n\}\). Then, \(V(M(K_{1,n})) = V(K_{1,n}) \cup \mathcal{M}\), where \(\mathcal{M} = \{m_i \mid 1 \le i \le n\}\).

If \(S = \mathcal{M}\), then S is a total dominating set of \(M(K_{1,n})\) with |S| = n, and hence \(\gamma_t(M(K_{1,n})) \le n\). On the other hand, using [9, Proposition 3.1], \(n = \gamma(M(K_{1,n})) \le \gamma_t(M(K_{1,n}))\).

Proposition 2.4. For any double star graph \(S_{1,n,n}\) on 2n+1 vertices, with \(n \geq 1\), we have

\[\gamma_t(M(S_{1,n,n})) = 2n.\]

Proof. Fix \(V(S_{1,n,n}) = \{v_0, v_1, \dots, v_{2n}\}\) and \(E(S_{1,n,n}) = \{v_0v_i, v_iv_{n+i} \mid 1 \leq i \leq n\}\). Then \(V(M(S_{1,n,n})) = V(S_{1,n,n}) \cup \mathcal{M}\), where \(\mathcal{M} = \{m_i, m_{i(n+i)} \mid 1 \leq i \leq n\}\).

Since \(S = \mathcal{M}\) is a total dominating set of \(M(S_{1,n,n})\) with |S| = 2n, then \(\gamma_t(M(S_{1,n,n})) \leq 2n\).

On the other hand, let S be a total dominating set \(M(S_{1,n,n})\). By Lemma 2.1, we can assume that \(S \subseteq \mathcal{M}\). Since, for every \(1 \le i \le n\), \(N_{M(S_{1,n,n})}(v_{n+i}) = \{m_{i(n+i)}\}\), then \(m_{i(n+i)} \in S\) for every \(1 \le i \le n\). Similarly, for every \(1 \le i \le n\), \(N_{M(S_{1,n,n})}(m_{i(n+i)}) = \{m_i, v_i, v_{n+i}\}\) implies that \(m_i \in S\) for every \(1 \le i \le n\), and hence \(\mathcal{M} \subseteq S\). This implies that \(\gamma_t(M(S_{1,n,n})) \ge 2n\).

Proposition 2.5. For any path \(P_n\) of order \(n \geq 3\),

\[\gamma_t(M(P_n)) = \lceil \frac{2n}{3} \rceil.\]

Proof. Fix \(V(P_n) = \{v_1, \dots, v_n\}\) and \(E(P_n) = \{v_i v_{i+1} \mid 1 \le i \le n-1\}\). Then \(V(M(P_n)) = V \cup \mathcal{M}\) where \(V = V(P_n)\) and \(\mathcal{M} = \{m_{i(i+1)} \mid 1 \le i \le n-1\}\).

If \(n \equiv 0 \mod 3\), then consider

\[S = \{m_{12}, m_{23}, m_{45}, m_{56}, \dots, m_{(n-2)(n-1)}, m_{(n-1)n}\}.\]

We have that S is a total dominating set of \(M(P_n)\) with \(|S| = \frac{2n}{3}\). If \(n \equiv 1 \mod 3\), then consider

\[S = \{m_{12}, m_{23}, m_{45}, m_{56}, \dots, m_{(n-3)(n-2)}, m_{(n-2)(n-1)}\} \cup \{m_{(n-1)n}\}.\]

We have that S is a total dominating set of \(M(P_n)\) with \(|S| = \lceil \frac{2n}{3} \rceil\). If \(n \equiv 2 \mod 3\), then consider

\[S = \{m_{12}, m_{23}, m_{45}, m_{56}, \dots, m_{(n-4)(n-3)}, m_{(n-3)(n-2)}\} \cup \{m_{(n-2)(n-1)}, m_{(n-1)n}\}.\]

We have that S is a total dominating set of \(M(P_n)\) with \(|S| = \lceil \frac{2n}{3} \rceil\). This implies \(\gamma_t(M(P_n)) \le \lceil \frac{2n}{3} \rceil\).

On the other hand, let S be a total dominating set for \(M(P_n)\). For every \(i=1,\ldots,n-2\), let \(G_i=P_n[v_i,v_{i+1},v_{i+2}]\). Since S dominates all vertices of the graph \(M(G_i),|S\cap V(M(G_i))|\geq 2\). This implies that \(|S|\geq \lceil \frac{2n}{3}\rceil\).

Since if we delete a vertex from a complete graph \(K_{n+1}\) we obtain a graph isomorphic to \(K_n\), Lemma 2.2 gives us the following result.

Lemma 2.6. For any \(n \geq 3\), we have

\[\gamma_t(M(K_n)) \le \gamma_t(M(K_{n+1})) \le \gamma_t(M(K_n)) + 1.\]

Proposition 2.7. Let \(K_n\) be the complete graph on \(n \geq 2\) vertices. Then

\[\gamma_t(M(K_n)) = \lceil \frac{2n}{3} \rceil\]

Proof. If \(2 \le n \le 4\), a direct computation shows that \(\gamma_t(M(K_n)) = \lceil \frac{2n}{3} \rceil\). Assume now \(n \ge 5\). The graph \(K_n\) has several subgraphs isomorphic to \(P_n\), and hence \(M(K_n)\) has subgraphs isomorphic to \(M(P_n)\). Fix one of those and consider S a total dominating set of \(M(P_n)\). Since S is also a total dominating set for \(M(K_n)\), we have \(\gamma_t(M(K_n)) \le \lceil \frac{2n}{3} \rceil\).

We will prove the opposite inequality by induction. Assume that we have equality for \(\gamma_t(M(K_n))\)and we want to prove it for \(\gamma_t(M(K_{n+1}))\). If \(n \equiv 2 \mod 3\), then \(n+1 \equiv 0 \mod 3\), and hence, \(\gamma_t(M(K_n)) = \lceil \frac{2n}{3} \rceil = \lceil \frac{2(n+1)}{3} \rceil\). On the other hand, by Lemma 2.6, \(\gamma_t(M(K_n)) \leq\)\(\gamma_t(M(K_{n+1}))\). This fact, together with the first part of the proof, implies that \(\gamma_t(M(K_{n+1})) =\)\(\lceil \frac{2(n+1)}{3} \rceil\). If \(n \equiv 0, 1 \mod 3\), by Lemma 2.6 and the first part of the proof, it is enough to show that \(\gamma_t(M(K_n)) < \gamma_t(M(K_{n+1}))\). As a contradiction, assume that \(\gamma_t(M(K_n)) = \gamma_t(M(K_{n+1}))\). If \(n \equiv 0 \mod 3\), then \(n-1 \equiv 2 \mod 3\), and hence this would implies \(\gamma_t(M(K_{n-1})) =\)\(\gamma_t(M(K_n)) = \gamma_t(M(K_{n+1}))\). Similarly, if \(n \equiv 1 \mod 3\), then \(n+1 \equiv 2 \mod 3\), and hence \(\gamma_t(M(K_n)) = \gamma_t(M(K_{n+1})) = \gamma_t(M(K_{n+2}))\). Hence we need to show that \(\gamma_t(M(K_n)) < \gamma_t(M(K_n))\)\(\gamma_t(M(K_{n+2}))\), when \(n \geq 4\). Let S be a total dominating set of \(M(K_{n+2})\). To fix the notation, assume \(V(K_{n+2}) = \{v_1, \dots, v_{n+2}\}\) and \(V(M(K_{n+2})) = V(K_{n+2}) \cup \mathcal{M}\), where \(\mathcal{M} = \{m_{ij} \mid 1 \leq 1 \leq n \leq n \}\)\(i < j \le n+2\). By Lemma 2.1, we can assume that \(S \subseteq \mathcal{M}\). After possibly relabeling \(V(K_{n+2})\), we can assume that \(m_{(n+1)(n+2)} \in S\). Since S is a total dominating set of \(M(K_{n+2})\), then it contains at least one element of the form \(m_{i(n+1)}\) or \(m_{i(n+2)}\), for some \(i=1,\ldots,n\). By construction, \(M(K_n)\) is isomorphic to \(M(K_{n+2}[v_1,\ldots,v_n])\), this implies that, similarly to the proof of Lemma 2.6, we can construct S' a total dominating set of \(M(K_n)\) by exchanging a vertex of the form \(m_{i(n+1)}\) or \(m_{i(n+2)}\) with one of the form \(m_{ij}\) and just discarding \(m_{(n+1)(n+2)}\). This implies that |S'| < |S|, and hence \(\gamma_t(M(K_n)) < \gamma_t(M(K_{n+2}))\).

Theorem 2.8. Let G be any graph of order n. Then

\[\lceil \frac{2n}{3} \rceil \le \gamma_t(M(G)) \le n - 1\]

Proof. From G we can obtain graph isomorphic to \(K_n\) by adding all the necessary edges. This implies that we can see G as a subgraph of \(K_n\), and hence M(G) as a subgraph of \(M(K_n)\). Since any total dominating set of M(G) is also a total dominating set for \(M(K_n)\), this implies that \(\gamma_t(M(G)) \ge \gamma_t(M(K_n))\). We obtain the left inequality by Proposition 2.7.

Consider T a spanning tree of G and S a minimal total dominating set of M(T). By Lemma 2.1, we can assume that \(S \subseteq E(T)\). This implies that \(|S| \le |E(T)| = n - 1\). Since S is also a total dominating set of M(G), then \(\gamma_t(M(G)) \le n - 1\).

Remark 2.9. By Propositions 2.3 and 2.5, the inequalities of Theorem 2.8 are all sharp.

Theorem 2.10. If G is a graph with order n and there exists a subgraph of G isomorphic to \(P_n\), then

\[\gamma_t(M(G)) = \lceil \frac{2n}{3} \rceil.\]

Proof. Since G has a subgraph isomorphic to \(P_n\), then M(G) has a subgraph isomorphic to \(M(P_n)\). Moreover, any total dominating set of \(M(P_n)\) is also a total dominating set for M(G). By Proposition 2.5, this implies that \(\gamma_t(M(K_n)) \leq \lceil \frac{2n}{3} \rceil\). We conclude by Theorem 2.8.

Directly from Theorem 2.10, we obtain the following result.

Corollary 2.11. For any \(n \geq 3\),

\[\gamma_t(M(P_n)) = \gamma_t(M(C_n)) = \gamma_t(M(W_n)) = \gamma_t(M(K_n)) = \lceil \frac{2n}{3} \rceil.\]

Proposition 2.12. Let \(F_n\) be the friendship graph with \(n \geq 2\). Then

\[\gamma_t(M(F_n)) = 2n.\]

Proof. Fix \(V(F_n) = \{v_0, v_1, \dots, v_{2n}\}\) and \(E(F_n) = \{v_0v_1, v_0v_2, \dots, v_0v_{2n}\} \cup \{v_1v_2, v_3v_4, \dots, v_{2n-1}v_{2n}\}\). Then \(V(M(F_n)) = V(F_n) \cup \mathcal{M}\), where \(\mathcal{M} = \{m_i \mid 1 \le i \le 2n\} \cup \{m_{i(i+1)} \mid 1 \le i \le 2n - 1 \text{ and } i \text{ is odd}\}\).

Since \(S = \{m_{i(i+1)} \mid 1 \le i \le 2n-1 \text{ and } i \text{ is odd}\} \cup \{v_i \mid i \text{ is odd}\}\) is a total dominating set for \(M(F_n)\) with |S| = 2n, then \(\gamma_t(M(F_n)) \le 2n\).

On the other hand, since \(F_n\) is obtained by joining n copies of \(C_3\) at \(v_0\), any total dominating set S of \(M(F_n)\) induces a total dominating set of \(M(C_3)\) as subgraph of \(M(F_n)\). By Corollary 2.11, \(\gamma_t(M(C_3)) = 2\). This fact together with the fact that any two distinct copies of \(M(C_3)\) in \(M(F_n)\) share only \(v_0\) implies that \(|S| \geq 2n\). As a consequence, \(\gamma_t(M(F_n)) \geq 2n\).

Using Theorem 2.8, we can describe the total domination number of the middle graph of a complete bipartite graph.

Proposition 2.13. Let \(K_{n_1,n_2}\) be the complete bipartite graph with \(n_2 \ge n_1 \ge 2\). Then

\[\gamma_t(M(K_{n_1,n_2})) = \begin{cases} n_2 + \lceil \frac{2n_1 - n_2}{3} \rceil, & \text{if } n_1 \le n_2 \le 2n_1 - 1, \\ n_2, & \text{if } n_2 \ge 2n_1. \end{cases}\]

Proof. Fix \(V(K_{n_1,n_2}) = \{v_1, \dots, v_{n_1}, u_1, \dots, u_{n_2}\}\) and \(E(K_{n_1,n_2}) = \{v_i u_j \mid 1 \le i \le n_1, 1 \le j \le n_2\}\). Then we have \(V(M(K_{n_1,n_2})) = V(K_{n_1,n_2}) \cup \mathcal{M}\), where \(\mathcal{M} = \{m_{ij} \mid 1 \le i \le n_1, 1 \le j \le n_2\}\).

Assume first \(n_1 = n_2\). If \(n_1 \equiv 0 \mod 3\), then consider

\[S = \{m_{11}, m_{12}, m_{23}, m_{33}, \dots, m_{(n_1 - 1)n_1}, m_{n_1 n_1}\}.\]

By construction, S is a total dominating set of \(M(K_{n_1,n_2})\) and \(|S| = n_1 + \frac{n_1}{3} = n_2 + \frac{n_1}{3} = n_2 + \lceil \frac{2n_1 - n_2}{3} \rceil\). If \(n_1 \equiv 1 \mod 3\), then consider

\[S = \{m_{11}, m_{12}, m_{23}, m_{33}, \dots, m_{(n_1-2)(n_1-1)}, m_{(n_1-1)(n_1-1)}\} \cup \{m_{n_1(n_1-1)}, m_{n_1n_1}\}.\]

By construction, S is a total dominating set of \(M(K_{n_1,n_2})\) and \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)\(n_2 + \left\lceil \frac{2n_1 - n_2}{3} \right\rceil\). If \(n_1 \equiv 2 \mod 3\), then consider

\[S = \{m_{11}, m_{12}, m_{23}, m_{33}, \dots, m_{(n_1-1)(n_1-1)}, m_{(n_1-1)n_1}\} \cup \{m_{n_1n_1}\}.\]

By construction, S is a total dominating set of \(M(K_{n_1,n_2})\) and \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)\(n_2 + \left\lceil \frac{2n_1 - n_2}{3} \right\rceil\).

Assume that \(n_1 + 1 \le n_2 \le 2n_1 - 1\). Consider

\[S' = \{m_{11}, m_{1n_1+1}, \dots, m_{(n_2-n_1)(n_2-n_1)}, m_{(n_2-n_1)n_2}\}.\]

Let \(G = K_{n_1,n_2}[u_{n_2-n_1+1}, \dots, u_{n_1}, v_{n_2-n_1+1}, \dots, v_{n_1}]\). Then G is isomorphic to a graph of the form \(K_{n,n}\), where \(n=2n_1-n_2\). This implies that by the first part of the proof, we can construct S'' a total dominating set of M(G) with \(|S''| = 2n_1 - n_2 + \lceil \frac{2n_1 - n_2}{3} \rceil\). Consider \(S = S' \cup S''\). Then Sis a total dominating set of \(M(K_{n_1,n_2})\) and \(|S| = 2(n_2 - n_1) + 2n_1 - n_2 + \lceil \frac{2n_1 - n_2}{3} \rceil = n_2 + \lceil \frac{2n_1 - n_2}{3} \rceil\). This implies that if \(n_1 \le n_2 \le 2n_1 - 1\), then \(\gamma_t(M(K_{n_1,n_2})) \le n_2 + \lceil \frac{2n_1 - n_2}{3} \rceil\).

Assume now that \(n_2 \geq 2n_1\). Consider

\[S = \{m_{11}, m_{1n_1+1}, \dots, m_{n_1n_1}, m_{n_12n_1}\} \cup \{m_{n_12n_1+1}, \dots, m_{n_1n_2}\},\\]

then S is a total dominating set of \(M(K_{n_1,n_2})\) with \(|S|=n_2\), and hence, \(\gamma_t(M(K_{n_1,n_2}))\leq n_2\).

On the other hand, assume first \(n_1 = n_2\). By Theorem 2.8, we have \(\gamma_t(M(K_{n_1,n_2})) \ge\)\(\left\lceil \frac{2(n_1+n_2)}{3} \right\rceil = n_2 + \left\lceil \frac{2n_1-n_2}{3} \right\rceil.\)

Assume that \(n_1 + 1 \le n_2 \le 2n_1 - 1\). Let S be a total dominating set of \(M(K_{n_1,n_2})\). By Lemma 2.1, we can assume that \(S \subseteq \mathcal{M}\). The construction of the first part of the proof is optimal since S' and S'' have the smallest possible size by the argument discussed when \(n_1\,=\,n_2\) and \(n_2 \geq 2n_1\).

This implies that if \(n_1 \leq n_2 \leq 2n_1 - 1\), then \(\gamma_t(M(K_{n_1,n_2})) = n_2 + \lceil \frac{2n_1 - n_2}{3} \rceil\).

Assume that \(n_2 \geq 2n_1\), then by [9, Proposition 3.13], we have \(n_2 = \gamma(M(K_{n_1,n_2}))\)\(\gamma_t(M(K_{n_1,n_2})) \leq n_2\). This implies that \(\gamma_t(M(K_{n_1,n_2})) = n_2\).

3. The middle graph of a tree

Similarly to [9, Proposition 2.4], if we consider T a tree and we denote by \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)\(V(T) \mid d_T(v) = 1\) the set of leaves of T, then we have the following result.

Proposition 3.1. Let T be a tree with n > 2 vertices. Then

\[\gamma_t(M(T)) \ge |\operatorname{leaf}(T)|.\]

Proof. Fix leaf\((T) = \{v_1, \ldots, v_k\}\), for some \(k \leq n\). If n = 2, then T is isomorphic to \(P_2\) and hence \(\gamma_t(M(T)) = 2 = |\operatorname{leaf}(T)|\). Assume that \(n \geq 3\) and let S be a total dominating set of M(T). Then, for each \(i=1,\ldots,k,\) \(S\cap N_{M(T)}[v_i]\neq\emptyset\). Since, if \(i\neq j\), then \(N_{M(T)}[v_j]\cap N_{M(T)}[v_i]=\emptyset\), we have that \(|S| \ge k\). As a consequence, \(\gamma_t(M(T)) \ge k = |\operatorname{leaf}(T)|\).

Remark 3.2. Notice that by Proposition 2.3, the inequality described in Proposition 3.1 is sharp.

It is sufficient to add some assumptions on the diameter of a tree T, to compute γt(M(T)) explicitly.

Theorem 3.3. Let T be a tree of order n ≥ 4 with diam(T) = 3. Then

\[\gamma_t(M(T)) = \begin{cases} n-2, & \text{if there are two vertices with } d_T(v) \geq 3, \\ n-1, & \text{otherwise.} \end{cases}\]

Proof. The assumption that diam(T) = 3 implies that T is a tree which is obtained by joining central vertex v of K1,p and the central vertex w of K1,q where p + q = n − 2. Let leaf(T) = {vⁱ | 1 ≤ i ≤ n − 2} be the set of leaves of T. Obviously V (T) = leaf(T) ∪ {v, w} and | leaf(T)| = n − 2. Define vn−¹ = v and vⁿ = w.

Assume first that p, q ≥ 2, i.e. there are two vertices with d^T (u) ≥ 3. Since S = {mi(n−1) | 1 ≤ i ≤ p} ∪ {min | p + 1 ≤ i ≤ n − 2} is a total dominating set of M(T) with |S| = n − 2, then γt(M(T)) ≤ n − 2. On the other hand, by Proposition 3.1, we have γt(M(T)) ≥ n − 2.

Assume that p ≥ 2 and q = 1, i.e. there is only one vertex with d^T (u) ≥ 3. Let S be a total dominating set of M(T). By Lemma 2.1, we can assume that S ⊆ E(T). Since NM(T)(vi) = {mi(n−1)} for all 1 ≤ i ≤ p = n − 3 and NM(T)(vn−2) = {m(n−2)n}, then {mi(n−1) | 1 ≤ i ≤ p}∪{m(n−2)n} ⊆ S. Moreover, NM(T)(m(n−2)n) = {m(n−1)n, vn, vn−2} implies that m(n−1)ⁿ ∈ S. This implies that |S| ≥ n − 1, and hence γt(M(T)) ≥ n − 1. On the other hand, by Theorem 2.8, γt(M(T)) ≤ n − 1.

Assume that p, q = 1, i.e. there are no vertices with d^T (u) ≥ 3. This implies that T is isomorphic to P⁴ and n = 4, and hence by Proposition 2.5, γt(M(T)) = 3 = n − 1.

In general, the opposite implication of Theorem 3.3 does not hold as the next example shows.

Example 3.4. Let T be the tree in Figure 2. Then a direct computation shows that diam(T) = 4 and γt(M(T)) = 5 = n − 2.

Figure 2. A tree on 7 vertices.

Proposition 3.5. Let T be a tree of order n ≥ 3 with diam(T) = 2. Then

\[\gamma_t(M(T)) = n - 1.\]

Proof. The assumption that diam(T) = 2 implies that T is isomorphic to K1,n−1. As a consequence, by Proposition 2.3, that γt(M(T)) = n − 1.

Remark 3.6. By the proof of Theorem 3.3, differently from the case of domination (see [9, Theorem 3.2]), γt(M(G)) = n − 1 does not implies that G is isomorphic to K1,n−1.

4. Operations on graphs

In this section, similarly to [9], we study the total domination number of the middle graph of the corona, 2-corona and join with K^p of a graph.

Definition 4.1. The corona G ◦ K¹ of a graph G is the graph of order 2|V (G)| obtained from G by adding a pendant edge to each vertex of G.

Example 4.2. Consider the graph P3, then the graph P³ ◦ K¹ is the one in Figure 3.

Figure 3. The graph P³ ◦ K1.

Theorem 4.3. For any connected graph G of order n ≥ 2,

\[\gamma_t(M(G \circ K_1)) = n + \gamma(M(G)).\]

Proof. Fix V (G) = {v1, . . . , vn}. Then V (G◦K1) = {v1, . . . , v2n} and E(G◦K1) = {v1vn+1, . . . , vnv2n} ∪ E(G). Then V (M(G ◦ K1)) = V (G ◦ K1) ∪ M, where M = {mi(n+i) | 1 ≤ i ≤ n} ∪ {mij | viv^j ∈ E(G)}.

Let S ⁰ be a minimal dominating set of M(G). By construction, S = S ⁰ ∪ {mi(n+i) | 1 ≤ i ≤ n} is a total dominating set of M(G ◦ K1) with |S| = n + γ(M(G)). This implies that γt(M(G ◦ K1)) ≤ n + γ(M(G)).

On the other hand, let S be a total dominating set of M(G ◦ K1). By Lemma 2.1, we can assume that S ⊆ M. Since NM(G◦K1)(vn+i) = {mi(n+i)}, for all 1 ≤ i ≤ n, then mi(n+i) ∈ S, for all 1 ≤ i ≤ n. In addition, NM(G◦K1)(mi(n+i)) = {vⁱ , vn+i} ∪ NM(G)(vi), for all 1 ≤ i ≤ n, then NM(G)(vi) ∩ S 6= ∅, for all 1 ≤ i ≤ n. As a consequence, S ∩ E(G) is a dominating set of M(G) and hence |S| ≥ n + γ(M(G)). As a consequence, γt(M(G ◦ K1)) ≥ n + γ(M(G)).

Definition 4.4. The 2-corona G ◦ P² of a graph G is the graph of order 3|V (G)| obtained from G by attaching a path of length 2 to each vertex of G so that the resulting paths are vertex-disjoint.

Example 4.5. Consider the graph P3, then the graph P³ ◦ P² is the one in Figure 4.

Figure 4. The graph P³ ◦ P²

Theorem 4.6. For any connected graph G of order \(n \geq 2\),

\[\gamma_t(M(G \circ P_2)) = 2n.\]

Proof. Fix \(V(G) = \{v_1, \dots, v_n\}\). Then \(V(G \circ P_2) = \{v_1, \dots, v_{3n}\}\) and \(E(G \circ P_2) = \{v_i v_{n+i}, v_{n+i} v_{2n+i} \mid 1 \leq i \leq n\} \cup E(G)\). Then \(V(M(G \circ P_2)) = V(G \circ P_2) \cup \mathcal{M}\), where \(\mathcal{M} = \{m_{i(n+i)}, m_{(n+i)(2n+i)} \mid 1 \leq i \leq n\} \cup \{m_{ij} \mid v_i v_j \in E(G)\}\).

Let S be a total dominating set of \(M(G \circ P_2)\). By Lemma 2.1, we can assume that \(S \subseteq \mathcal{M}\). Since \(N_{M(G \circ P_2)}(v_{2n+i}) = \{m_{(n+i)(2n+i)}\}\), for every \(1 \leq i \leq n\), we have \(m_{(n+i)(2n+i)} \in S\) for every \(1 \leq i \leq n\). In addition, \(N_{M(G \circ P_2)}(m_{(n+i)(2n+i)}) = \{m_{i(n+i)}, v_{2n+i}, v_{n+i}\}\), for every \(1 \leq i \leq n\), implies that \(m_{i(n+i)} \in S\), for every \(1 \leq i \leq n\). This implies that \(|S| \geq 2n\), and hence \(\gamma_t(M(G \circ P_2)) \geq 2n\).

On the other hand, \(S = \{m_{i(n+i)}, m_{(n+i)(2n+i)} \mid 1 \leq i \leq n\}\) is a total dominating set of \(M(G \circ P_2)\) with |S| = 2n. This implies that \(\gamma_t(M(G \circ P_2)) \leq 2n\).

Definition 4.7. The join G + H of two graphs G and H is the graph with vertex set \(V(G + H) = V(G) \cup V(H)\) and edge set \(E(G + H) = E(G) \cup E(H) \cup \{vw \mid v \in V(G), w \in V(H)\}.\)

Example 4.8. Consider the graphs \(G = K_3\) and \(H = P_2\), then graph G + H is the one in Figure 5.

Figure 5. The graph \(K_3 + P_2\).

Theorem 4.9. For any connected graph G of order \(n \geq 2\),

\[\gamma_t(M(G + \overline{K_p})) = \begin{cases} p, & \text{if } p \ge 2n, \\ \lceil \frac{2(n+p)}{3} \rceil, & \text{if } \frac{n}{2} \le p \le 2n - 1. \end{cases}\]

Proof. Fix \(V(G) = \{v_1, \dots, v_n\}\) and \(V(\overline{K_p}) = \{v_{n+1}, \dots, v_{n+p}\}\). Then \(V(M(G + \overline{K_p})) = V(G + \overline{K_p}) \cup \mathcal{M}_1 \cup \mathcal{M}_2\) where \(\mathcal{M}_1 = \{m_{ij} \mid v_i v_j \in E(G)\}\) and \(\mathcal{M}_2 = \{m_{\underline{i(n+j)}} \mid 1 \leq i \leq n, 1 \leq j \leq p\}\).

Case \(p \geq 2n\). Let S be a total dominating set of \(M(G + \overline{K_p})\). By Lemma 2.1, we can assume \(S \subseteq \mathcal{M}_1 \cup \mathcal{M}_2\). Since, if \(j \neq k\), \(N_{M(G + \overline{K_p})}(v_{n+j}) \cap N_{M(G + \overline{K_p})}(v_{n+k}) = \emptyset\), then for every \(1 \leq j \leq p\) there exists \(1 \leq i \leq n\) such that \(m_{i(n+j)} \in S\), and hence \(|S| \geq p\). As a consequence, \(\gamma_t(M(G + \overline{K_p})) \geq p\). On the other hand, \(S = \{m_{i(n+i)}, m_{i(2n+i)} \mid 1 \leq i \leq n\} \cup \{m_{1(3n+i)} \mid 1 \leq i \leq p-2n\}\) is a total dominating set of \(M(G + \overline{K_p})\) with |S| = p. This implies that \(\gamma_t(M(G + \overline{K_p})) \leq p\).

Case p = 2n - 1. Since \(S = \{m_{i(n+i)}, m_{i(2n+i)} \mid 1 \le i \le n-1\} \cup \{m_{n(2n)}, m_{n(2n-1)}\}\) is a total dominating set of \(M(G + \overline{K_{2n-1}})\) with |S| = 2n, then \(\gamma_t(M(G + \overline{K_{2n-1}})) \le 2n\). On the other hand, by Theorem 2.8, \(\gamma_t(M(G + \overline{K_{2n-1}})) \ge \lceil \frac{2(3n-1)}{3} \rceil = 2n\), and hence \(\gamma_t(M(G + \overline{K_{2n-1}})) = 2n = \lceil \frac{2(n+p)}{3} \rceil\).

Case \(n+3 \le p \le 2n-2\). Assume that p=n+k with \(3 \le k \le n-2\). The graph \(G+\overline{K_p}\) has k subgraphs isomorphic to \(P_3\) and one subgraph isomorphic to \(P_{2(n-k)}\) that are all disjoint. In fact,

the k subgraphs \((G+\overline{K_p})[v_1,v_{n+1},v_{2n+1}],\ldots,(G+\overline{K_p})[v_k,v_{n+k},v_{2n+k}]\) are all isomorphic to \(P_3\) and the subgraph \((G+\overline{K_p})[v_{k+1},\ldots,v_n,v_{n+k+1},\ldots,v_{2n}]\) has a subgraph isomorphic to \(P_{2(n-k)}\). By Proposition 2.5, \(\gamma_t(M(G+\overline{K_p})) \leq 2k + \lceil \frac{2(2(n-k))}{3} \rceil = \lceil \frac{2(n+p)}{3} \rceil\). By Theorem 2.8, we obtain the desired equality.

Case p = n + 2. If \(n \equiv 0 \mod 3\), consider

\[S = \{m_{1(n+1)}, m_{1(n+2)}, m_{2(n+3)}, m_{3(n+3)}, \dots, m_{(n-1)(2n)}, m_{n(2n)}, m_{n(2n+1)}, m_{n(2n+2)}\}.\]

Then S is a total dominating set of \(M(G + \overline{K_p})\) with \(|S| = \lceil \frac{2(n+p)}{3} \rceil\). If \(n \equiv 1 \mod 3\), consider

\[S = \{m_{1(n+1)}, m_{1(n+2)}, m_{2(n+3)}, m_{3(n+3)}, \dots, m_{n(2n)}, m_{n(2n+1)}, m_{n(2n+2)}\}.\]

Then S is a total dominating set of \(M(G + \overline{K_p})\) with \(|S| = \lceil \frac{2(n+p)}{3} \rceil\). If \(n \equiv 2 \mod 3\), consider

\[S = \{m_{1(n+1)}, m_{1(n+2)}, m_{2(n+3)}, m_{3(n+3)}, \dots, m_{n(2n+1)}, m_{n(2n+2)}\}.\]

Then S is a total dominating set of \(M(G+\overline{K_p})\) with \(|S|=\lceil \frac{2(n+p)}{3} \rceil\). This implies that \(\gamma_t(M(G+\overline{K_p})) \leq \lceil \frac{2(n+p)}{3} \rceil\). By Theorem 2.8, we then obtain that \(\gamma_t(M(G+\overline{K_p})) = \lceil \frac{2(n+p)}{3} \rceil\).

Case \(n-1 \leq p \leq n+1\). If p=n-1, then the graph \(G+\overline{K_p}\) contains the path \(P: v_1v_{n+1}v_2v_{n+2}\cdots v_{n+p}v_n\). If p=n, then \(G+\overline{K_p}\) contains the path \(P': v_1v_{n+1}v_2v_{n+2}\cdots v_{n+p-1}v_nv_{n+p}\). If p=n+1, then \(G+\overline{K_p}\) contains the path \(P'': v_{n+1}v_1v_{n+2}v_2v_{n+3}\cdots v_{n+p-1}v_nv_{n+p}\). Since the paths P,P' and P'' are all isomorphic to \(P_{n+p}\), we can apply Theorem 2.10, and obtain that \(\gamma_t(M(G+\overline{K_p}))=\lceil \frac{2(n+p)}{3}\rceil\).

Case \(\frac{n}{2} \leq p \leq n-2\). Assume that p=n-k with \(2 \leq k \leq \frac{n}{2}\). If n is even and \(p=\frac{n}{2}\) (or equivalently \(k=\frac{n}{2}\)), then the set \(S=\{m_{i(n+i)},m_{(i+\frac{n}{2})(n+i)}\mid 1\leq i\leq \frac{n}{2}\}\) is a total dominating set of \(M(G+\overline{K_p})\) with \(|S|=n=\lceil \frac{2(n+p)}{3}\rceil\). As a consequence, \(\gamma_t(M(G+\overline{K_p}))\leq \lceil \frac{2(n+p)}{3}\rceil\), and by Theorem 2.8, we obtain the desired equality.

Assume that \(2 \leq k \leq \frac{n}{2}-1\). The graph \(G+\overline{K_p}\) has k subgraphs isomorphic to \(P_3\) and one subgraph isomorphic to \(P_{2(n-2k)}\) that are all disjoint. In fact, the k induced subgraphs \((G+\overline{K_p})[v_1,v_{n+1},v_{k+1}],\ldots,(G+\overline{K_p})[v_k,v_{n+k},v_{2k}]\) are all isomorphic to \(P_3\) and the induced subgraph \((G+\overline{K_p})[v_{2k+1},\ldots,v_n,v_{n+k+1},\ldots,v_{2n-k}]\) has a subgraph isomorphic to \(P_{2(n-2k)}\). By Proposition 2.5, this implies that \(\gamma_t(M(G+\overline{K_p})) \leq 2k + \lceil \frac{2(2(n-2k))}{3} \rceil = \lceil \frac{2(n+p)}{3} \rceil\). By Theorem 2.8, we obtain the desired equality.

Similarly to [9], when p is small relatively to n, \(\gamma_t(M(G+\overline{K_p}))\) is strongly related to \(\gamma_t(M(G))\).

Theorem 4.10. For any connected graph G of order \(n \ge 2\) and any integer \(1 \le p \le \frac{n}{2} - 1\),

\[\lceil \frac{2(n+p)}{3} \rceil \le \gamma_t(M(G+\overline{K_p})) \le\]

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

|A| = n - 2p, G[A] has no isolated vertices\(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\).

Proof. Fix V (G) = {v1, . . . , vn} and V (Kp) = {vn+1, . . . , vn+p}. Then V (M(G+Kp)) = V (G+ Kp)∪M1∪M² where M¹ = {mij | viv^j ∈ E(G)} and M² = {mi(n+j) | 1 ≤ i ≤ n, 1 ≤ j ≤ p}. By Theorem 2.8, we obtain the first inequality. Let now A ⊆ V (G) be a subset with |A| = n − 2p and suppose G[A] has no isolated vertices. Without loss of generalities, we can suppose that A = {v2p+1, . . . , vn}. Consider S ⁰ be a minimal total dominating set of M(G[A]), then S = S ⁰ ∪ {mi(n+i) , m(p+i)(n+i) | 1 ≤ i ≤ p} is a total dominating set of M(G + Kp). Since this arguments works for every A ⊆ V (G) such that |A| = n − 2p and G[A] has no isolated vertices, we obtain the second inequality.

If we apply Lemma 2.2 to the graph G + K1, we obtain the following result.

Lemma 4.11. Let G be a graph of order n ≥ 2 with no isolated vertices. Then

\[\gamma_t(M(G)) \le \gamma_t(M(G + \overline{K_1})) \le \gamma_t(M(G)) + 1.\]

Notice that both inequalities described in Lemma 4.11 are sharp as we can see form the following examples.

Example 4.12. Consider the graph G = C5. Then G + K¹ is isomorphic to W6. This implies that by Corollary 2.11, γt(M(G)) = 4 = γt(M(G + K1)).

Figure 6. The graph P³ + K1.

Example 4.13. Consider the graph G = P3. Then G + K¹ is the graph in Figure 6. By Proposition 2.5 and Theorem 2.10, we have that γt(M(P3)) = 2 and γt(M(P³ + K1)) = 3.

Proposition 4.14. For any star graph K1,n on n + 1 vertices, with n ≥ 4, we have

\[\gamma_t(M(K_{1,n} + \overline{K_1})) = n.\]

Proof. Fix V (K1,n) = {v0, v1, . . . , vn}, V (K1) = {vn+1} and E(K1,n) = {v0v1, v0v2, . . . , v0vn}. Then V (M(K1,n +K1)) = V (K1,n)∪M, where M = {mⁱ | 1 ≤ i ≤ n}∪ {mi(n+1) | 0 ≤ i ≤ n}. By Proposition 2.3 and Lemma 4.11, γt(M(K1,n + K1)) ≥ n. On the other hand, since S = {mⁱ | 1 ≤ i ≤ n − 2} ∪ {m(n−1)(n+1), mn(n+1)} is a total dominating set of M(K1,n + K1) with |S| = n, then γt(M(K1,n + K1)) ≤ n.

Remark 4.15. Proposition 4.14 shows that the upper bound of Theorem 4.10 is sharp. In fact, if A ⊆ V (K1,n) with |A| = n − 2 and G[A] has no isolated vertices, then G[A] is isomorphic to K1,n−2, and hence by Proposition 2.3, γt(M(G[A])) = n − 2.

Proposition 4.16. Let G be a graph of order \(n \ge 2\) and \(1 \le p \le \frac{n}{2} - 1\). If G has a subgraph isomorphic to a path graph \(P_n\), then

\[\gamma_t(M(G+\overline{K_p})) = \lceil \frac{2(n+p)}{3} \rceil.\]

Proof. By hypothesis, the graph \(G+\overline{K_p}\) contains a subgraph isomorphic to \(P_{n+p}\). By Theorem 2.10 we obtain the desired equality.

As a direct consequence of Proposition 4.16, we obtain the following result.

Corollary 4.17. Let G be a graph of order \(n \ge 2\) and \(1 \le p \le \frac{n}{2} - 1\). If G is isomorphic to a path graph \(P_n\), or a cycle graph \(C_n\), or a wheel graph \(W_n\), or a complete graph \(K_n\), then

\[\gamma_t(M(G+\overline{K_p})) = \lceil \frac{2(n+p)}{3} \rceil.\]

5. Nordhaus-Gaddum relations

Since the work [11] appeared, several other authors studied Nordhaus-Gaddum type relations for many graph invariants. We refer to [1] for a survey on the subject.

Theorem 5.1. Consider a graph G on \(n \ge 2\) vertices such that G and \(\overline{G}\) have no isolated vertices and no components isomorphic to \(K_2\). Then

\[2(n-1) \ge \gamma_t(M(G)) + \gamma_t(M(\overline{G})) \ge 2\lceil \frac{2n}{3} \rceil\]

and

\[(n-1)^2 \ge \gamma_t(M(G)) \cdot \gamma_t(M(\overline{G})) \ge (\lceil \frac{2n}{3} \rceil)^2.\]

Proof. By applying Theorem 2.8 to each component of G and \(\overline{G}\), we obtain that \(n-1 \geq \gamma_t(M(G)) \geq \lceil \frac{2n}{3} \rceil\) and \(n-1 \geq \gamma_t(M(\overline{G})) \geq \lceil \frac{2n}{3} \rceil\).

Remark 5.2. If in Theorem 5.1 we allow G or \(\overline{G}\) to have components isomorphic to \(K_2\), then the described upper bounds might not work. To see this it is enough to consider the graph \(C_4\). In fact, \(\overline{C_4}\) consists of two copies of \(K_2\), and then \(\gamma_t(M(C_4)) = 3\) and \(\gamma_t(M(\overline{C_4})) = 4\).

As the next example shows, all the inequalities of Theorem 5.1 are sharp.

Example 5.3. Consider the graph \(P_4\), then by Proposition 2.5, we have \(\gamma_t(M(P_4)) = 3\). On the other hand, \(\overline{P_4}\) is isomorphic to \(P_4\), and hence \(\gamma_t(M(\overline{P_4})) = 3\). Since n = 4, then \(6 = \gamma_t(M(P_4)) + \gamma_t(M(\overline{P_4})) = 2(n-1) = 2\lceil \frac{2n}{3} \rceil\), and \(9 = \gamma_t(M(P_4)) \cdot \gamma_t(M(\overline{P_4})) = (n-1)^2 = (\lceil \frac{2n}{3} \rceil)^2\).

Acknowledgement

During the preparation of this article the fourth author was supported by JSPS Grant-in-Aid for Early-Career Scientists (19K14493).

References

• [1] M. Aouchiche and P. Hansen, A survey of Nordhaus-Gaddum type relations, Discrete Applied Mathematics, 161 (2013), 466–546.
• [2] J.A. Bondy and U.S.R. Murty, Graph theory, Graduate texts in mathematics, vol. 244, Springer Science and Media, 2008.
• [3] E.J. Cockayne, R.M. Dawes, and S.T. Hedetniemi, Total domination in graphs, Networks, 10 (1980), 211–219.
• [4] T. Hamada and I. Yoshimura, Traversability and connectivity of the middle graph of a graph, Discrete Mathematics, 14 (1976) 247–255.
• [5] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
• [6] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
• [7] M.A. Henning and A. Yeo, Total domination in graphs, Springer Monographs in Mathematics, 2013.
• [8] F. Kazemnejad and S. Moradi, Total domination number of central graphs, Bulletin of the Korean Mathematical Society, 56 (4) (2019), 1059–1075.
• [9] F. Kazemnejad, B. Pahlavsay, E. Palezzato and M. Torielli, Domination number of middle graphs. ArXiv:2008.02975.
• [10] F. Kazemnejad, B. Pahlavsay, E. Palezzato, and M. Torielli, Total dominator coloring number of middle graphs. To appear in Discrete Mathematics, Algorithms and Applications, 2022.
• [11] E.A. Nordhaus and J.W. Gaddum, On complementary graphs, Amer. Math. Monthly, 63 (1956), 175–177.
• [12] L. Ouldrabah, M. Blidia, and A. Bouchou, Roman domination in oriented trees, Electronic Journal of Graph Theory and Applications, 9 (1) (2021), 95–103.
• [13] B. Pahlavsay, E. Palezzato, and M. Torielli, 3-tuple total domination number of rook's graphs. Discussiones Mathematicae Graph Theory, 42 (2022), 15–37
• [14] B. Pahlavsay, E. Palezzato, and M. Torielli, Domination in latin square graphs. Graphs and Combinatorics, 37 (3) (2021), 971–985.