A question involving a chess piece called a prince on the \(8\times 8\) chessboard leads to a concept in graph theory involving total domination in the Cartesian products of paths and cycles. A vertex \(u\) in a graph \(G\) totally dominates a vertex \(v\) if \(v\) is adjacent to \(u\). A subset \(S\) of the vertex set of a graph \(G\) is a total dominating set for \(G\) if every vertex of \(G\) is totally dominated by at least one vertex of \(S\). If \(S\) is a total dominating set of a graph \(G\), then \(S(v)\) denotes the number of vertices in \(S\) that totally dominate \(v\). A total dominating set \(S\) in a graph \(G\) is called a proper total dominating set if \(S(u) \ne S(v)\) for every two adjacent vertices \(u\) and \(v\) of \(G\). It is shown that \(C_n \ \Box \ K_2\) possesses a proper total dominating set if and only if \(n\ge 4\) is even and the graph \(C_n \ \Box \ P_m\) possesses a proper total dominating set for every even integer \(n \ge 4\) and every integer \(m \ge 3\). Furthermore, \(C_3 \ \Box \ P_m\) possesses a proper total dominating set if and only if \(m = 3\). If \(n\ge 5\) is an odd integer and \(m\equiv 3 \pmod 4\), then \(C_n \ \Box \ P_m\) has a proper total dominating set. If at least one of \(n\) and \(m\) is even, then \(C_n \ \Box \ C_m\) has a proper total dominating set. The graphs \(C_n \ \Box \ C_m\) are further studied when both \(n\) and \(m\) are odd. Other results and questions are also presented.
In [3], a chess piece called a \(k\)-prince where \(1 \le k \le 14\) was introduced. When placed on a square of the standard \(8 \times 8\) chessboard, a \(k\)-prince can move horizontally and/or vertically a total of exactly \(k\) squares (vacant or not) away from its current position. A \(k\)-prince can attack or dominate a square if the \(k\)-prince can move to the square. A 1-prince, also referred to more simply as a prince, can therefore move to one square adjacent to where the prince is located. Since the prince can only move one square horizontally or vertically from its given position, this is similar to a possible movement of the standard chess piece rook, although a rook is permitted to move any number of squares horizontally or vertically (but not both) away from its current position. If princes are appropriately placed on the squares of an \(8\times 8\) chessboard, then each square can be dominated. Indeed, this is the case if a prince is placed on every square. It is known that 20 princes (but no fewer) can be placed on 20 squares of an \(8 \times 8\) chessboard so that every square is dominated exactly once. In fact, in the placement of the 20 princes shown in Figure 1(a) each square is dominated exactly once. Furthermore, in the placement of the 40 princes shown in Figure 1(b) each square is dominated exactly twice.
This brings up an opposite question.
Question 1.1. Is there a placement of princes on the \(8 \times 8\) chessboard so that no two squares are dominated the same number of times?
The answer to this question is No.
This then suggests another question.
Question 1.2. Is there a placement of princes on the \(8 \times 8\) chessboard so that no two adjacent squares are dominated the same number of times?
Before answering this question, we discuss some related information.
One of the most popular research areas in graph theory in recent years is domination. While this area evidently began with the work of Berge [1] in 1958 and Ore [9] in 1962, it wasn’t until 1977 when this area become an active area of research with the appearance of a survey paper [6] by Cockayne and Hedetniemi. Since then, many variations of domination have been introduced and studied. One of the best known of these is total domination, whose definition is simple.
A vertex \(u\) in a graph \(G\) totally dominates a vertex \(v\) if \(v\) is adjacent to \(u\). A set \(S\) of vertices in \(G\) is a total dominating set if every vertex of \(G\) is totally dominated by at least one vertex of \(S\). A graph \(G\) has a total dominating set if and only if \(G\) contains no isolated vertices. Total domination was introduced by Cockayne, Dawes and Hedetniemi [5] in 1977. It has been referred to as a core concept of graph domination by Haynes, Hedetniemi, and Henning in their 2023 book [7]. The 2013 book by Henning and Yeo [8] deals exclusively with total domination in graphs. We refer to the books [2, 7] for notation and terminology not defined here.
Let \(G\) be a graph with a total dominating set \(S\). Then every vertex \(v\) of \(G\) is totally dominated by one or more vertices of \(S\). Let \( _S(v)\) denote the number of vertices in \(S\) that totally dominate \(v\). While no total dominating set \(S\) in a graph \(G\) has the property that \( _S(u) \ne _S(v)\) for every two vertices \(u\) and \(v\) of \(G\), it is possible that \( _S(u) \ne _S(v)\) for every two adjacent vertices \(u\) and \(v\) of \(G\).
A graph \(G\) is sometimes called locally irregular if \(\deg u \ne \deg v\) for every two adjacent vertices \(u\) and \(v\) of \(G\). If \(G\) is locally irregular, then \(V(G)\) is a total dominating set with this property. A total dominating set \(S\) in a graph \(G\) is proper if \( _S(u) \ne _S(v)\) for every two adjacent vertices \(u\) and \(v\) of \(G\). As we mentioned, every graph without isolated vertices has a total dominating set. On the other hand, not all graphs without isolated vertices contain proper total dominating sets. Our interest here is in graphs that do possess such sets.
For paths and cycles, the following are known (see [4]).
Proposition 1.3. [4] For an integer \(n \ge 2\), the path \(P_n\) of order \(n\) has a proper total dominating set if and only if \(n\equiv 3 \ (\mathrm{mod}\ 4)\).
Proposition 1.4. [4] For an integer \(n \ge 3\), the cycle \(C_n\) of order \(n\) has a proper total dominating set if and only if \(n\equiv 0 \ (\mathrm{mod}\ 4)\).
For integers \(n\) and \(m\) with \(n \ge m\ge 1\), the Cartesian product \(P_n \ \Box \ P_m\) of the path \(P_n\) of order \(n\) and the path \(P_m\) of order \(m\) is referred to as a grid graph. In particular, \(P_n \ \Box \ P_1\cong P_n\).
The answer to Question 1.2 then depends on whether the graph \(P_8 \ \Box \ P_8\) has a proper total dominating set. This question, and more, was answered in [4].
Theorem 1.5. [4] For every two integers \(n, m \ge 2\), the grid graph \(P_n \ \Box \ P_m\) possesses a proper total dominating set.
We now turn our attention to graphs that are Cartesian products of paths and cycles.
For positive integers \(n\) and \(m\) with \(n\ge 3\), the Cartesian product \(C_n \ \Box \ P_m\) of the cycle \(C_n\) of order \(n\) and the path \(P_m\) of order \(m\) is referred to as a cylindrical graph. In particular, \(C_n \ \Box \ P_1\cong C_n\). The graph \(C_n \ \Box \ P_2= C_n \ \Box \ K_2\) is often referred to as a prism. Those prisms with a proper total dominating set have been determined.
Theorem 2.1. [4] The prism \(C_n \ \Box \ K_2\) possesses a proper total dominating set if and only if \(n\ge 4\) is even.
The cylindrical graph \(C_n \ \Box \ P_m\) is constructed from \(m\) copies \(Q_1\), \(Q_2\), \(\ldots\), \(Q_m\) of \(n\)-cycles where \(Q_i\) \(=\) (\(u_{i,1}\), \(u_{i,2}\), \(\ldots\), \(u_{i, n}\), \(u_{i, 1}\)) for \(1 \le i \le m\) such that \(u_{i, j}u_{i+1, j} \in E(G)\) for \(1 \le i \le m-1\) and \(1\le j \le n\). For a cycle \(Q=(x_1, x_2, \ldots, x_n, x_1)\) of order \(n\) in a graph \(G\) and a set \(S\) of vertices in \(G\), let \( _S(Q)=( _S(x_1), _S(x_2), \ldots, _S(x_n))\).
By Theorem 2.1, for every even integer \(n \ge 4\), the prism \(C_n \ \Box \ K_2\) possesses a proper total dominating set. In fact, this result can be extended to the cylindrical graphs \(C_n \ \Box \ P_m\) for every even integer \(n\) and all integers \(m \ge 3\).
Theorem 2.2. For each even integer \(n \ge 4\) and each integer \(m \ge 3\), the graph \(C_n \ \Box \ P_m\) possesses a proper total dominating set.
Proof. Let the cylindrical graph \(G = C_n \ \Box \ P_m\) be constructed from \(m\) copies \(Q_1\), \(Q_2\), \(\ldots\), \(Q_m\) of \(n\)-cycles where \(Q_i\) \(=\) (\(u_{i,1}\), \(u_{i,2}\), \(\ldots\), \(u_{i, n}\), \(u_{i, 1}\)) for \(1 \le i \le m\) such that \(u_{i, j}u_{i+1, j} \in E(G)\) for \(1 \le i \le m-1\) and \(1\le j \le n\). We consider two cases, according to whether \(m\) is even or \(m\) is odd.
Case 1. \(m \ge 4\) is even. For \(1 \le i \le m\), the set \(S_i\) is defined by \[S_i=\left\{ \begin{array}{cl} \{u_{i, j}: \mbox{ $j$ is even and $2 \le j \le n$}\}, & \mbox{ if $i$ is odd},\\ V(Q_i), & \mbox{ if $i$ is even}. \end{array} \right.\]
Let \(S = S_1\cup S_2\cup \cdots \cup S_m\). We show that \(S\) is a proper total dominating set. Observe that \[\begin{aligned} _S(Q_1) =& (\underline{3, 1}, \ \underline{3, 1}, \ldots, \ \underline{3, 1}), \\ _S(Q_i) =& \left\{ \begin{array}{ll} (\underline{2, 4}, \underline{2, 4}, \ldots, \underline{2, 4}) & \mbox{ if $i$ is even, and $2 \le i \le m-2$},\\ (\underline{4, 2}, \underline{4, 2}, \ldots, \underline{4, 2}) & \mbox{ if $i$ is odd and $3 \le i \le m-1$}, \end{array}\right.\\ _S(Q_m) =& (\underline{2, 3}, \ \underline{2, 3}, \ldots, \ \underline{2, 3}). \end{aligned}\]
Since \( _S(x)\ne _S(y)\) for every two adjacent vertices \(x\) and \(y\) in \(G\), it follows that \(S\) is a proper total dominating set of \(G\).
Case 2. \(m \ge 3\) is odd. Then \(m+1\ge 4\) is even. Let \(G'=C_n \ \Box \ P_{m+1}\) and let \(G= C_n \ \Box \ P_m\) be constructed from \(C_n \ \Box \ P_{m+1}\) by deleting the last row \(Q_{m+1}\). For \(1 \le i \le m\), the set \(S_i\) is defined by \[S_i=\left\{ \begin{array}{cl} \{u_{i, j}: \mbox{ $j$ is even and $2 \le j \le n$}\}, & \mbox{ if $i$ is odd},\\ V(Q_i), & \mbox{ if $i$ is even and $2 \le i \le m-1$.} \end{array} \right.\]
Let \(S = S_1\cup S_2\cup \cdots \cup S_m\). We show that \(S\) is a proper total dominating set of \(G\). Observe that \[\begin{aligned} _S(Q_1) =& _S(Q_m)= (\underline{3, 1}, \ \underline{3, 1}, \ldots, \ \underline{3, 1}), \\ _S(Q_i) =& \left\{ \begin{array}{ll} (\underline{2, 4}, \underline{2, 4}, \ldots, \underline{2, 4}) , & \mbox{ if $i$ is even, and $2 \le i \le m-1$},\\ (\underline{4, 2}, \underline{4, 2}, \ldots, \underline{4, 2}), & \mbox{ if $i$ is odd and $3 \le i \le m-2$.} \end{array}\right. \end{aligned}\]
Since \( _S(x)\ne _S(y)\) for every two adjacent vertices \(x\) and \(y\) in \(G\), it follows that \(S\) is a proper total dominating set of \(G\). ◻
It was shown in [4] that \(C_3 \ \Box \ P_2\) does not have a proper total dominating set. However, the graph \(C_3 \ \Box \ P_3\) does possess a proper total dominating set, as shown in Figure 2 where the solid vertices are those belong to a proper total dominating set. In fact, \(C_3 \ \Box \ P_3\) is an exception for the graphs \(C_3 \ \Box \ P_n\) for \(n \ge 2\). In order show this fact, we first present a lemma.
Lemma 2.3. For \(n \ge 6\), let \(C_3 \ \Box \ P_n\) be constructed from the \(n\) triangles \(T_i= (u_{i}, v_{i}, w_{i}, u_i)\) for \(1 \le i \le n\) by adding the edges \(u_iu_{i+1}\), \(v_iv_{i+1}\), \(w_iw_{i+1}\) for \(1 \le i \le n-1\). If \(S\) is a proper total dominating set of the graph \(C_3 \ \Box \ P_n\) where \(n \ge 6\) such that \((a)\) \(( _S(w_4), _S(v_4), _S(u_4))=(1, 3, 2)\), \((b)\) \(w_4, w_{5}, v_{5} \in S\), and \((c)\) \(v_4, u_{4}, u_{5} \notin S\), then \(\{\)\( _S(w_{j})\), \( _S(v_{j})\), \( _S(u_{j})\)\(\}\)\(=\)\(\{1, 2, 3\}\) for all \(j\) with \(4 \le j\le n-1\).
Proof. Let \(G = C_3 \ \Box \ P_n\) where \(n \ge 6\). By the hypothesis (a), it follows that \(\{\)\( _S(w_{4})\), \( _S(v_{4})\), \( _S(u_{4})\)\(\}\)\(=\)\(\{1, 2, 3\}\).
Since \(u_4u_{5} \in E(G)\) and \( _S(u_4)= 2\), it follows that \( _S(u_{5})= 3\) and \(u_{6} \in S\). Consequently, \( _S(w_{5})= 2\) and \(w_{6} \notin S\). Therefore, \( _S(v_{5})= 1\) and \(v_{6} \notin S\). Thus,
\(\{\)\( _S(w_{5})\), \( _S(v_{5})\), \( _S(u_{5})\)\(\}\)\(=\)\(\{1, 2, 3\}\).
This completes the proof if \(n=6\). Suppose then that \(n \ge 7\).
Proceeding as above, we see that \(( _S(w_{6}), _S(v_{6}), _S(u_{6}))=(3, 2, 1)\), \(w_{7}, u_{7} \in S\) and \(v_{7} \notin S\). Therefore, \(\{\)\( _S(w_{6})\), \( _S(v_{6})\), \( _S(u_{6})\)\(\}\)\(=\)\(\{1, 2, 3\}\), which verifies the lemma if \(n = 7\). Suppose then that \(n \ge 8\). Continuing in this manner, we arrive the following:
(1) \(( _S(w_{7}), _S(v_{7}), _S(u_{7}))=(1, 3, 2)\), completing the proof if \(n = 8\),
(2) \(( _S(w_{8}), _S(v_{8}), _S(u_{8}))=(2, 1, 3)\), completing the proof if \(n = 9\),
(3) \(( _S(w_{9}), _S(v_{9}), _S(u_{9}))=(3, 2, 1)\), completing the proof if \(n = 10\),
(4) \(( _S(w_{10}), _S(v_{10}), _S(u_{10}))=(1, 3, 2)\), completing the proof if \(n = 11\).
Furthermore, \(w_{10}, w_{11} , v_{11} \in S\) and \(v_{10}, u_{10}, u_{11} \notin S\). Therefore, the situation for \(w_j\), \(v_j\), \(u_j\), \(w_{j+1}\), \(v_{j+1}\), \(u_{j+1}\) when \(j = 10\) is precisely that when \(j = 4\). Let \(k\) be the greatest integer such that \(k \equiv 4 \pmod 6\) and \(k \le n-2\). Continuing as above, we see that \(( _S(w_k), _S(v_k), _S(u_k))=(1, 3, 2)\), \(w_{k}, w_{k+1}, v_{k+1} \in S\), and \(v_{k}, u_{k}, u_{k+1} \notin S\). Thus, for every integer \(j\) with \(k \le j \le n-2\), we have \(\{ _S(w_j), _S(v_j), _S(u_j)\}=\{1, 2, 3\}\) and so for all integers \(j\) with \(4 \le j \le n-2\), \(\{ _S(w_j), _S(v_j), _S(u_j)\}=\{1, 2, 3\}\). ◻
The proof of Lemma 2.3 is illustrated in Figure 3, where a vertex in \(S\) is denoted by \(\bullet\) and a vertex not in \(S\) is denoted by \(\Box\). In particular, \((w_4, v_4, u_4)=(\bullet, \Box, \Box)\) indicates that \(w_4 \in S\) and \(v_4, u_4 \notin S\). Thus, for \(i = 4\), we saw that \(( _S(w_4), _S(v_4), _S(u_4))=( _S(w_{10}), _S(v_{10}), _S(u_{10}))=(1, 3, 2)\), \(w_{10}, w_{11}, v_{11} \in S\) and \(v_{10}, u_{10}, u_{11} \notin S\). Thus, \((w_{4}, v_{4}, u_{4})= (w_{10}, v_{10}, u_{10})=(\bullet, \Box, \Box)\) and \((w_{5}, v_{5}, u_{5})= (w_{11}, v_{11}, u_{11})=(\bullet, \bullet, \Box)\).
Theorem 2.4. Let \(n \ge 2\) be an integer. The graph \(C_3 \ \Box \ P_n\) possesses a proper total dominating set if and only if \(n = 3\).
Proof. We saw that \(C_3 \ \Box \ P_3\) possesses a proper total dominating set. Thus, it remains to show that for each integer \(n \ge 4\), the graph \(G = C_3 \ \Box \ P_n\) does not possess a proper total dominating set. Assume, to the contrary, that there is an integer \(n \ge 4\) such that \(G\) possesses a proper total dominating set \(S\). As before, let \(G\) be constructed from the \(n\) triangles \(T_i= (u_{i}, v_{i}, w_{i}, u_i)\) for \(1 \le i \le n\) by adding the edges \(u_iu_{i+1}\), \(v_iv_{i+1}\), \(w_iw_{i+1}\) for \(1 \le i \le n-1\). Since \(\chi(C_3)=3\) and \(\deg u_1=\deg v_1=\deg w_1=3\), it follows that \(\{ _S(u_1), _S(v_1), _S(w_1)\}=\{1, 2, 3\}\). We may assume that \( _S(u_1)=1\), \( _S(v_1)=2\), and \( _S(w_1)=3\). Thus, \(u_1, v_1, w_2\in S\) and \(w_1, u_2 \notin S\), which implies that \(v_2\in S\). Since \( _S(v_2)\in \{2, 3\}\) and \(v_1v_2\in E(G)\), it follows that \( _S(v_2) = 3\) and \(v_3 \in S\). Since \( _S(u_2)\in \{3, 4\}\) and \(u_2v_2\in E(G)\), it follows that \( _S(u_2) = 4\) and \(u_3 \in S\). From this information, we now have the following observation as well.
Observation 2.5. The set \(\{ _S(u_n), _S(v_n), _S(w_n)\}=\{1, 2, 3\}\). Furthermore, exactly two of the vertices \(u_n, v_n, w_n\) belong to \(S\), and \(4 \in \{ _S(u_{n-1}), _S(v_{n-1})\), \( _S(w_{n-1})\}\).
Now, either \( _S(w_2) = 1\) or \( _S(w_2) = 2\). We claim that \( _S(w_2) = 1\). Assume, to the contrary, that \( _S(w_2) = 2\). This implies that \(w_3 \in S\). Since \(v_2v_3 \in E(G)\) and \( _S(v_2)=3\), it follows that \( _S(v_3)=4\) and \(v_4 \in S\). Consequently, \( _S(w_3)=3\) and \(w_4 \notin S\). Therefore, \( _S(u_3)=2\) and \(u_4 \notin S\).
If \(n = 4\), then \( _S(u_4)=2\), which contradicts the fact that \( _S(u_3)=2\) and \(u_3u_4 \in E(G)\). Suppose now that \(n \ge 5\). In this case, it follows that \( _S(u_4)=3\) and \(u_5 \in S\). Since \( _S(w_4)\in \{2, 3\}\), \(w_3w_4 \in E(G)\), and \( _S(w_3)=3\), it follows that \( _S(w_4)= 2\) and \(w_5 \notin S\). This implies that \( _S(v_4)=1\) and \(v_5 \notin S\). Since \( _S(u_5)\ge 1\), this is impossible if \(n = 5\). If \(n \ge 6\), then \( _S(u_5)= _S(w_5)=1\) since \( _S(w_4) = 2\) and \(w_4w_5 \in E(G)\). Since \(u_5w_5 \in E(G)\), this is impossible. Thus, as claimed, \( _S(w_2) = 1\).
Since \( _S(w_2) = 1\), it follows that \(w_3 \notin S\). This in turn implies that \( _S(v_3)=2\) and \(v_4 \notin S\). Also, \( _S(u_3)=1\) and so \(u_4 \notin S\). Since \( _S(w_4) \ge 1\), it follows that \( _S(w_4) =1\) and \(w_5 \in S\). Since it is impossible that \( _S(u_4), _S(v_4) \in \{1, 2\}\), it follows that \(w_4 \in S\), which implies that \( _S(w_3)=4\). Since \(v_3v_4 \in E(G)\) and \( _S(v_3)= 2\), it follows that \( _S(v_4)=3\) and \(v_5 \in S\). Furthermore, \( _S(u_4)=2\) and \(u_5 \notin S\).
We now know that \((a)\) \(( _S(w_4), _S(v_4), _S(u_4))=(1, 3, 2)\), \((b)\) \(w_4, w_{5} , v_{5} \in S\), and \((c)\) \(v_5, u_{4}, u_{5}, \notin S\). By Lemma 2.3, \(\{ _S(w_{n-1}), _S(v_{n-1}), _S(u_{n-1})\}=\{1, 2, 3\}\). This, however, contradicts Observation 1. ◻
Proposition 2.6. Let \(n\ge 5\) be an odd integer. If \(m \ge 3\) is an integer such that \(m\equiv 3 \pmod 4\), then \(C_n \ \Box \ P_m\) has a proper total dominating set.
Proof. Let the cylindrical graph \(G=C_n \ \Box \ P_m\) be constructed from \(m\) copies \(Q_1, Q_2, \ldots,Q_m\) of \(n\)-cycles where \(Q_i = (u_{i,1}, u_{i,2}, \ldots,u_{i,n}, u_{i,1})\) for \(1\leq i\leq m\) such that \(u_{i,j} u_{i+1,j} \in E(G)\) for \(1\leq i \leq m-1\) and \(1\leq j\leq n\). For \(1\leq i \leq m\), let the set \(S_i\) be defined by \[S_i = \begin{cases} V(Q_i) – \{u_{i,1}\} & \text{if } i\equiv 2 \hspace{-.3cm}\pmod 4, \\ \{u_{i,j} : j \text{ is odd and $1\leq j \leq m$}\} & \text{if $i$ is odd},\\ V(Q_i) – \{u_{i,1}, u_{i,2}, u_{i,m}\} & \text{if } i \equiv 0\hspace{-.3cm} \pmod 4. \end{cases}\]
Let \(S = S_1 \cup S_2 \cup \dots \cup S_m\). We show that \(S\) is a proper total dominating set. Observe that \[\begin{aligned} gma_S(Q_1)=& gma_S(Q_m) = (\underline{1,3}, \ldots,\underline{1,3}, 2),\\ gma_S(Q_i) =& \left\{\begin{array}{ll} (4,1,4, \underline{2,4},…, \underline{2,4}, 2, 3) ,& \text{if $i\equiv 2\hspace{-.3cm}\pmod 4$ and },\\ (1,3,2,\underline{4,2},…, \underline{4,2}) ,& \text{if $i$ is odd and $3\leq i \leq m-1$},\\ (2,1,3, \underline{2,4},…, \underline{2,4}, 1, 3) ,& \text{if $i\equiv 4\hspace{-.3cm}\pmod 4$.} \end{array}\right. \end{aligned}\]
Since \( gma_S(x) \neq gma_S(y)\) for every two adjacent vertices \(x\) and \(y\) in \(G\), it follows that \(S\) is a proper total dominating set of \(G\). ◻
An extensive case-by-case analysis shows the following.
Proposition 2.7. The cylindrical graph \(C_5 \ \Box \ P_4\) does not have a proper total dominating set.
On the other hand, \(C_5 \ \Box \ P_5\) has a proper total dominating set as shown in Figure 4.
Problem 2.8. Let \(n\) and \(m\) be integers where \(n \ge 5\) is odd integer and \(m \ge 6\) and \(m \not\equiv 3 \pmod 4\). Which cylindrical graphs \(C_n \ \Box \ P_m\) possess a proper total dominating set?
For integers \(n\) and \(m\) with \(n, m \ge 3\), the Cartesian product \(C_n \ \Box \ C_m\) of the cycle \(C_n\) and the cycle \(C_m\) is referred to as a cyclical graph.
Theorem 3.1. Let \(n\) and \(m\) be integers where \(n, m \ge 3\). If at least one of \(n\) and \(m\) is even, then \(C_n \ \Box \ C_m\) has a proper total dominating set.
Proof. Let the cyclical graph \(G = C_n \ \Box \ C_m\) be constructed from \(m\) copies \(Q_1, Q_2, \ldots, Q_m\) of \(n\)-cycles where \(Q_i\) \(=\) (\(u_{i,1}\), \(u_{i,2}\), \(\ldots\), \(u_{i, n}\), \(u_{i, 1}\)) for \(1 \le i \le m\) such that (a) \(u_{i, j}u_{i+1, j} \in E(G)\) for \(1 \le i \le m-1\) and \(1\le j \le n\) and (b) \(u_{m, j}u_{1, j} \in E(G)\) and \(1\le j \le n\). We consider two cases.
Case 1. \(n\) and \(m\) are both even. Thus, \(n, m \ge 4\). For \(1 \le i \le m\), the set \(S_i\) is defined by \[S_i=\left\{ \begin{array}{cl} \{u_{i, j}: \mbox{ $j$ is even and $2 \le j \le n$}\} & \mbox{ if $i$ is odd},\\ V(Q_i) & \mbox{ if $i$ is even and $2 \le i \le m-2$},\\ V(Q_i)-\{u_{i, m}\} & \mbox{ if $i= m$.}\\ \end{array} \right.\]
Let \(S = S_1\cup S_2\cup \cdots \cup S_m\). We show that \(S\) is a proper total dominating set of \(G\). Observe that \[\begin{aligned} _S(Q_1) =& _S(Q_{m-1})= (\underline{4, 2}, \underline{4, 2}, \ldots, \underline{4, 2}, \underline{4, 1}),\\ _S(Q_i) =& \left\{ \begin{array}{ll} (\underline{2, 4}, \underline{2, 4}, \ldots, \underline{2, 4}) & \mbox{ if $i$ is even, and $2 \le i \le m-2$},\\ (\underline{4, 2}, \underline{4, 2}, \ldots, \underline{4, 2}) & \mbox{ if $i$ is odd and $3 \le i \le m-1$}, \end{array}\right.\\ _S(Q_m) =& (\underline{1, 4}, \underline{2, 4}, \underline{2, 4}, \ldots, \underline{2, 4}, \underline{1, 4}). \end{aligned}\]
Since \( _S(x)\ne _S(y)\) for every two adjacent vertices \(x\) and \(y\) in \(G\), it follows that \(S\) is a proper total dominating set of \(G\).
Case 2. Exactly one of \(n\) and \(m\) is even. We may assume that \(n \ge 4\) is even and \(m \ge 3\) is odd. For \(1 \le i \le m\) and \(i \ne 3\), the set \(S_i\) is defined by \[S_i=\left\{ \begin{array}{cl} \{u_{i, j}: \mbox{ $j$ is even and $2 \le j \le n$}\} & \mbox{ if $i=1$ or $i$ is even and $4 \le i \le m-1$},\\ V(Q_i) & \mbox{ if $i = 2$ or $i$ is odd and $5 \le i \le m$.}\\ \end{array} \right.\]
Let \(S = S_1\cup S_2\cup S_4 \cup S_5 \cup \cdots \cup S_m\). We show that \(S\) is a proper total dominating set of \(G\). If \(m = 3\), then \[\begin{aligned} _S(Q_1) =& (\underline{3, 1}, \underline{3, 1}, \ldots, \underline{3, 1}),\\ _S(Q_2) =& (\underline{2, 3}, \underline{2, 3}, \ldots, \underline{2, 3}),\\ _S(Q_3) =& (\underline{1, 2}, \underline{1, 2}, \ldots, \underline{1, 2}).\\ \end{aligned}\]
If \(m \ge 5\), then \[\begin{aligned} _S(Q_1) =& (\underline{4, 2}, \underline{4, 2}, \ldots, \underline{4, 2}),\\ _S(Q_2) =& (\underline{2, 3}, \underline{2, 3}, \ldots, \underline{2, 3}),\\ _S(Q_3) =& (\underline{1, 2}, \underline{1, 2}, \ldots, \underline{1, 2}),\\ _S(Q_4) =& (\underline{3, 1}, \underline{3, 1}, \ldots, \underline{3, 1}),\\ _S(Q_i) =& \left\{ \begin{array}{ll} (\underline{2, 4}, \underline{2, 4}, \ldots, \underline{2, 4}) & \mbox{ if $i$ is odd, and $5 \le i \le m$},\\ (\underline{4, 2}, \underline{4, 2}, \ldots, \underline{4, 2}) & \mbox{ if $i$ is even and $6 \le i \le m-1$.} \end{array}\right. \end{aligned}\]
Since \( _S(x)\ne _S(y)\) for every two adjacent vertices \(x\) and \(y\) in \(G\), it follows that \(S\) is a proper total dominating set of \(G\). ◻
We are now left with the question: For which odd integers \(n, m \ge 3\), does the cyclical graph \(C_n \ \Box \ C_m\) possess a proper total dominating set? We first consider the case where \(m=n=3\).
Proposition 3.2. The cyclical graph \(C_3 \ \Box \ C_3\) does not possess a proper total dominating set.
Proof. Assume, to the contrary, that \(G = C_3 \ \Box \ C_3\) possesses a proper total dominating set \(S\). Let \(G\) be constructed from the three triangles \(T_i= (u_{i}, v_{i}, w_{i}, u_i)\) for \(1 \le i \le 3\) by adding the edges \(u_iu_{i+1}\), \(v_iv_{i+1}\), \(w_iw_{i+1}\) for \(1 \le i \le 2\) and \(u_1u_3, v_1v_3, w_1w_3\). Since \(G\) is 4-regular, it follows that \( _S(x) \in \{1, 2, 3, 4\}\) for every vertex \(x\) of \(G\). Thus, \(\{ _S(v_1), _S(v_2), _S(v_3)\}\) is one of \(\{1, 2, 3\}\), \(\{1, 2, 4\}\), \(\{1,3, 4\}\), \(\{2, 3, 4\}\). We consider these four cases.
Case 1. \(\{ _S(v_1), _S(v_2), _S(v_3)\} = \{1, 2, 3\}\). Assume, without loss of generality, that \( _S(v_2)= 3\) and \(u_2, v_1, v_3 \in S\) and \(w_2\notin S\). We may further assume that \( _S(v_1)=1\) and \( _S(v_3)= 2\). Since \( _S(v_1)=1\) and \(v_3 \in S\), it follows that \(u_1, v_2, w_1 \notin S\). This implies that \( _S(w_1)= 2\) and so \(w_3 \in S\). Since \( _S(v_3)= 2\), it follows that \(u_3 \notin S\). However then, \( _S(u_1)= _S(w_1) = 2\), which is a contradiction since \(u_1w_1\in E(G)\).
Case 2. \(\{ _S(v_1), _S(v_2), _S(v_3)\} = \{1, 2, 4\}\). Assume, without loss of generality, that \( _S(v_1)=1\), \( _S(v_2)= 4\), and \( _S(v_3)= 2\). Hence, \(N(v_2) \subseteq S\) and \(u_1, v_2, w_1 \notin S\). Since \( _S(v_3)= 2\), we may assume that \(u_3 \notin S\) and \(w_3 \in S\). However then, \( _S(v_3)= _S(w_3) = 2\), which is a contradiction since \(v_3w_3 \in E(G)\).
Case 3. \(\{ _S(v_1), _S(v_2), _S(v_3)\} = \{1, 3, 4\}\). Assume, without loss of generality, that \( _S(v_1)=1\), \( _S(v_2)= 4\), and \( _S(v_3)= 3\). Hence, \(N(v_2) \subseteq S\) and \(u_1, v_2, w_1 \notin S\). Since \( _S(v_3)= 3\) and \(v_2 \notin S\), it follows that \(u_3, w_3 \in S\). However then, \( _S(v_3)= _S(w_3) = 3\), which is a contradiction since \(v_3w_3 \in E(G)\).
Case 4. \(\{ _S(v_1), _S(v_2), _S(v_3)\} = \{2, 3, 4\}\). Assume, without loss of generality, that \( _S(v_1)=2\), \( _S(v_2)= 4\), and \( _S(v_3)= 3\). Hence, \(N(v_2) \subseteq S\). Since \( _S(v_1)=2\), at least one of \(u_1, w_1\) is not in \(S\), say \(u_1 \notin S\). Since \( _S(v_1)=2\) and \(u_1 \notin S\), it forces \( _S(w_1)=3\) and so \(w_3\in S\). However then, \( _S(u_3)=3\), which is impossible since \(u_3v_3\in E(G)\). ◻
Next, we show that for each odd integer \(m \ge 5\), the graph \(C_3 \ \Box \ C_m\) does not have a proper total dominating set. In order to show this, we first present some preliminary information. Let \(G = C_3 \ \Box \ C_m\) be constructed from the \(m\) triangles \((u_{i}, v_{i}, w_{i}, u_i)\) for \(1 \le i \le m\) by adding the edges \(u_iu_{i+1}\), \(v_iv_{i+1}\), \(w_iw_{i+1}\) for \(1 \le i \le m-1\) and \(u_1u_m, v_1v_m, w_1w_m\).
Lemma 3.3. Let \(m \ge 5\) be an odd integer. If \(G = C_3 \ \Box \ C_m\) has a proper total dominating set \(S\), then \(G[S]\) is \(C_3\)-free.
Proof. Assume, to the contrary, that there is an odd integer \(m\ge 5\) such that \(G = C_3 \ \Box \ C_m\) has a proper total dominating set \(S\) for which \(C_3 \subseteq G[S]\). We may assume that \((u_{3}, v_{3}, w_{3}, u_3) \subseteq G[S]\). Since \( _S(u_3)\ge 2\), \( _S(v_3)\ge 2\), and \( _S(w_3)\ge 2\), it follows that \(\{ _S(u_3), _S(v_3), _S(w_3)\} = \{2, 3, 4\}\). Assume, without loss of generality, that \( _S(u_3)=2\), \( _S(v_3)= 3\), and \( _S(w_3)= 4\). Hence, \(N(w_3)=\{u_3, v_3, w_2, w_4\} \subseteq S\) and \(u_2, u_4 \notin S\). Since \( _S(v_3)= 3\), we may further assume that \(v_2\in S\) and \(v_4 \notin S\). Since \( _S(u_3)=2\) and \( _S(u_4)\in \{2, 3\}\), it follows that \( _S(u_4)= 3\) and so \(u_5 \in S\). This forces
(i) \( _S(v_4) = 2\) and so \(v_5 \notin S\) and
(ii) \( _S(w_4) = 1\) and so \(w_5 \notin S\).
Hence, \( _S(u_5)=1\) and \( _S(v_5)\in \{1, 2\}\). Since \( _S(v_4)= 2\) and \( _S(u_5)=1\), this is impossible. ◻
Lemma 3.4. Let \(m \ge 5\) be an odd integer. If \(G = C_3 \ \Box \ C_m\) has a proper total dominating set \(S\), then \( _S(x) \ne 4\) for every vertex \(x\) of \(G\).
Proof. Assume, to the contrary, that there is an odd integer \(m\ge 5\) such that \(G = C_3 \ \Box \ C_m\) has a proper total dominating set \(S\) for which \( _S(x)= 4\) for some vertex \(x\) of \(G\). Thus, there is an integer \(i\) with \(1 \le i \le m\) such that \(4 \in \{ _S(u_i), _S(v_i), _S(w_i)\}\). Hence, \(\{ _S(u_i), _S(v_i), _S(w_i)\}\) is one of the three sets \(\{2, 3, 4\}\), \(\{1, 3, 4\}\), and \(\{1, 2, 4\}\). We consider these three cases.
Case 1. \(\{ _S(u_i), _S(v_i), _S(w_i)\}=\{2, 3, 4\}\). We may assume that \(i = 2\) and \( _S(u_2)=2\), \( _S(v_2)=4\), and \( _S(w_2)=3\). Thus, \(N(v_2) \subseteq S\) and so \(v_2 \notin S\) by Lemma 3.3. Since \( _S(w_2)=3\) and \(v_2 \notin S\), it follows that \(w_1, w_3\in S\). Since \( _S(u_2)=2\), exactly one of \(u_1\) and \(u_3\) belongs to \(S\), say \(u_1 \notin S\) and \(u_3\in S\). However then, \(C_3 = (u_3, v_3, w_3, u_3) \in G[S]\), which is impossible by Lemma 3.3. Hence, \(\{ _S(u_i), _S(v_i), _S(w_i)\}\ne \{2, 3, 4\}\) for \(1 \le i \le m\).
Case 2. \(\{ _S(u_i), _S(v_i), _S(w_i)\}=\{1, 3, 4\}\). We may assume that \(i = 2\) and \( _S(u_2)=1\), \( _S(v_2)=4\), and \( _S(w_2)=3\). Thus, \(N(v_2) \subseteq S\) and so \(v_2 \notin S\) by Lemma 3.3. Since \( _S(w_2)=3\) and \(v_2 \notin S\), it follows that \(w_1, w_3\in S\). Since \( _S(u_2)=1\), it follows that \(u_1, u_3 \notin S\). Then \( _S(u_3)= 3\) or \( _S(u_3)= 4\). First, suppose that \( _S(u_3)= 3\). Then \(u_4\notin S\). Since \( _S(w_2)=3\) and \( _S(w_3) \in \{2, 3\}\), it follows that \( _S(w_3)=2\) and so \(w_4 \notin S\). Since \( _S(w_3)=2\) and \( _S(v_3) \in \{1, 2\}\), it follows that \( _S(v_3)= 1\) and so \(v_4\notin S\). This forces \( _S(u_4)=1\). However then, \( _{S}(w_4) \in \{1, 2\}\) and \(\{ _S(u_4), _S(v_4)\}= \{1, 2\}\), which is impossible. Hence, we may assume that \( _S(u_3)= 4\). Thus, \(N(u_3) \in S\). Then \( _S(w_3) = 2\) and \(w_4 \notin S\). This implies that \( _S(v_3) = 1\) and \(v_4 \notin S\). That is, \(( _S(u_3), _S(v_3), _S(w_3))=(4, 1, 2)\). This forces \( _S(u_4)=1\) and \(u_5 \in S\). Since \( _S(w_4)\in \{2, 3\}\) and \( _S(w_3)=2\), it follows that \( _S(w_4)=3\) and \(u_4, w_5 \in S\). Hence, \( _S(v_4) =2\) and \(v_5 \notin S\). If \(m = 5\), then \( _S(w_5)= _S(u_5)=2\), a contradiction.
We now assume that \(m \ge 7\). Applying the argument above, we obtain the following:
\(\star\) \(( _S(u_3), _S(v_3), _S(w_3))=(4, 1, 2)\) and \(u_3 \notin S\) and \(v_3, w_3 \in S\),
\(\star\) \(( _S(u_4), _S(v_4), _S(w_4))=(1, 2, 3)\) and \(u_4 \in S\) and \(v_4, w_4 \notin S\),
\(\star\) \(( _S(u_5), _S(v_5), _S(w_5))=(2, 3, 1)\) and \(u_5, w_5 \in S\) and \(v_5 \notin S\), and
\(\star\) \(( _S(u_6), _S(v_6), _S(w_6))=(3, 1, 2)\) and \(v_6 \in S\) and \(u_6, w_6 \notin S\).
Furthermore, \(u_7, v_7 \in S\) and \(w_7 \notin S\). If \(m = 7\), then \( _S(v_1)= _S(w_1)=2\), a contradiction. We now assume that \(m \ge 9\). Continuing as above, we obtain the following:
\(\star\) \(( _S(u_7), _S(v_7), _S(w_7))=(1, 2, 3)\) and \(u_7, v_7 \in S\) and \(w_7 \notin S\) and
\(\star\) \(( _S(u_8), _S(v_8), _S(w_8))=(2, 3, 1)\) and \(u_8, v_8 \notin S\) and \(w_8 \in S\).
Furthermore, \(u_9, \notin S\) and \(v_9, w_9 \in S\). If \(m = 9\), then \( _S(v_1)= _S(v_9)=2\), a contradiction. We now assume that \(m \ge 11\). Continuing as above, we obtain the following:
\(\star\) \(( _S(u_9), _S(v_9), _S(w_9))=(3, 1, 2)\) and \(u_9 \notin S\) and \(v_9, w_9 \in S\), and
\(\star\) \(( _S(u_{10}), _S(v_{10}), _S(w_{10}))=(1, 2, 3)\) and \(u_{10}, v_8 \in S\) and \(v_{10}, w_{10} \notin S\).
Furthermore, \(u_{11}, w_{11} \in S\) and \(v_{11} \notin S\). Observe that \[( _S(u_{10}), _S(v_{10}), _S(w_{10}))=( _S(u_{4}), _S(v_{4}), _S(w_{4})) = (1, 2, 3),\] \[(u_{10}, v_{10}, w_{10}) = (u_{4}, v_{4}, w_{4}) = (\bullet, \ \Box, \ \Box),\] \[(u_{11}, v_{11}, w_{11}) = (u_{5}, v_{5}, w_{5}) = (\bullet, \ \Box, \ \bullet).\]
Hence, as in the case when \(m = 5\), if \(m = 11\), then \( _S(u_{11})= _S(w_{11})=2\), a contradiction.
In general, for each odd integer \(m \ge 13\),
\(\star\) if \(m \equiv 1 \pmod 6\), then \( _S(v_1)= _S(w_1)=2\),
\(\star\) if \(m \equiv 3 \pmod 6\), then \( _S(v_1)= _S(v_m)=2\), and
\(\star\) if \(m \equiv 5 \pmod 6\), then \( _S(u_m)= _S(w_m)=2\).
In any case, a contradiction is produced. Hence, \(\{ _S(u_i), _S(v_i), _S(w_i)\}\ne \{1, 3, 4\}\) for \(1 \le i \le m\).
Case 3. \(\{ _S(u_i), _S(v_i), _S(w_i)\}=\{1, 2, 4\}\). We may assume that \(i = 2\) and \( _S(u_2)=1\), \( _S(v_2)=4\), and \( _S(w_2)=2\). Thus, \(N(v_2) \subseteq S\) and \(u_1, u_3 \notin S\). Since \( _S(w_2)=2\), we may assume that \(w_1\notin S\) and \(w_3 \in S\). Since \( _S(w_3) \in \{2, 3\}\) and \( _S(w_2)=2\), it follows that \( _S(w_3)=3\). This implies that \( _S(u_3)=4\). Thus, \( _S(v_3)\in \{1, 2\}\). Therefore, \(\{ _S(u_3), _S(v_3), _S(w_3)\}=\{1, 3, 4\}\) or \(\{ _S(u_3), _S(v_3), _S(w_3)\}=\{2, 3, 4\}\). By Cases \(1\) and \(2\), this is impossible. ◻
Theorem 3.5. Let \(m \ge 5\) be an odd integer. The graph \(C_3 \ \Box \ C_m\) does not possess a proper total dominating set.
Proof. Assume, to the contrary, that \(G = C_3 \ \Box \ C_5\) possesses a proper total dominating set \(S\). By Lemma 3.4, it follows that \( _S(x) \in \{1, 2, 3\}\) for every vertex \(x\) of \(G\). Hence,
\[\{ _S(u_i), _S(v_i), _S(w_i)\}= \{1, 2, 3\},\] for \(1 \le i \le m\).
Assume, without loss of generality, that \(( _S(u_2), _S(v_2), _S(w_2))= (1, 3, 2)\). Since \( _S(v_2)= 3\), exactly three vertices in \(N(v_2)=\{v_1, u_2, v_3, w_2\}\) belong to \(S\).
1. If \(\{u_2, v_3, w_2\} \subseteq S\) or \(\{u_2, v_1, w_2\} \subseteq S\), say the former, then \(v_1 \notin S\) and \(v_2\notin S\) by Lemma 3.3. Since \( _S(u_2)=1\) and \(w_2 \in S\), it follows that \(u_1, u_3 \notin S\). See Figure 5(a).
2. If \(\{v_1, v_3, w_2\} \subseteq S\), then \(u_2\notin S\). Since \( _S(u_2)=1\) and \(w_2 \in S\), it follows that \(u_1, u_3, v_2 \notin S\). Since \( _S(w_2)=2\) and \(u_2, v_2 \notin S\), it follows that \(w_1, w_3\in S\). See Figure 5(b).
3. If \(\{u_2, v_1, v_3\} \subseteq S\), then \(w_2 \notin S\). Since \( _S(w_2)=2\) and \(u_2\in S\), exactly one of \(w_1, v_2, w_3\) belongs to \(S\). Thus, at least one of \(w_1\) and \(w_3\) does not belong to \(S\), say \(w_1 \notin S\). Thus, either \(v_2 \in S\) or \(w_3 \in S\) but not both. See Figure 5(c).
We consider these three cases.
Case 1. \(\{u_2, v_3, w_2\} \subseteq S\) and \(v_1\notin S\). As shown in Figure 5(a), since \( _S(w_2)= 2\) and \(u_2 \in S\), exactly one of \(w_1\) and \(w_3\) belongs to \(S\).
First, suppose that \(w_1 \notin S\) and \(w_3 \in S\). Hence, \( _S(u_3)=3\) and so \( _S(v_3)=2\) and \( _S(w_3)=1\). Since \( _S(w_3)=1\) and \(w_2, v_3 \in S\), this is impossible.
Next, suppose that \(w_1 \in S\) and \(w_3 \notin S\). A similar argument shows that
\(\star\) \(( _S(u_{3}), _S(v_{3}), _S(w_{3}))=(2, 1, 3)\) and \((u_{4}, v_{4}, w_{4}) =(\Box, \ \bullet, \ \bullet)\)
\(\star\) \(( _S(u_{4}), _S(v_{4}), _S(w_{4}))=(3, 2, 1)\) and \((u_{5}, v_{5}, w_{5}) =(\bullet, \ \Box, \Box)\).
If \(m = 5\), then \( _S(u_5)= 0\), which is impossible. Thus, \(m \ge 7\). Then
\(\star\) \(( _S(u_{5}), _S(v_{5}), _S(w_{5}))=(1, 3, 2)\) and \((u_{6}, v_{6}, w_{6}) =(\bullet, \ \bullet, \ \Box)\)
\(\star\) \(( _S(u_{6}), _S(v_{6}), _S(w_{6}))=(2, 1, 3)\) and \((u_{7}, v_{7}, w_{7}) =(\Box, \Box, \ \bullet)\).
If \(m = 7\), then \( _S(u_1)= _S(u_7) = 2\), a contradiction. If \(m \ge 9\), then we have the situation in Figure 6. Observe that \[( _S(u_{8}), _S(v_{8}), _S(w_{8}))=( _S(u_{2}), _S(v_{2}), _S(w_{2})) = (1, 3, 2),\] \[(u_{8}, v_{8}, w_{8}) = (u_{2}, v_{2}, w_{2}) = (\bullet, \ \Box, \ \bullet),\] \[(u_{9}, v_{9}, w_{9}) = (u_{3}, v_{3}, w_{3}) = (\Box, \ \bullet, \ \Box).\]
Hence, if \(m = 9\), then \( _S(u_{1})= _S(u_9)=2\), a contradiction.
In general, for each odd integer \(m \ge 11\),
\(\star\) if \(m \equiv 5 \pmod 6\), then \( _S(v_1)= _S(w_1)=1\) and
\(\star\) if \(m \equiv 3 \pmod 6\) or \(m \equiv 1 \pmod 6\), then \( _S(u_1)= _S(u_m)=2\).
In any case, a contradiction is produced.
Case 2. \(\{v_1, v_3, w_2\} \subseteq S\) and \(u_2 \notin S\). As shown in Figure 5(b), \(u_1, u_2, u_3, v_2 \notin S\) and \(w_1, w_3\in S\). Since \( _S(w_2)=2\) and \( _S(w_3) \in \{2, 3\}\), it follows that \( _S(w_3)= 3\) and so \(w_4\in S\). This forces \( _S(u_3) = 1\) and \( _S(v_3) =2\) and so \(u_4, v_4 \notin S\). Since \( _S(u_3)=2\) and \( _S(u_4) \in \{1, 2\}\), it follows that \( _S(u_4)= 1\) and so \(u_5 \notin S\). Since \( _S(w_3)=3\) and \( _S(u_4)= 1\), it forces \( _S(w_4) = 2\) and \( _S(v_4) =3\) and so \(v_5, w_5 \in S\). Observe that \[( _S(u_{4}), _S(v_{4}), _S(w_{4}))=( _S(u_{2}), _S(v_{2}), _S(w_{2})) = (1, 3, 2),\] \[(u_{4}, v_{4}, w_{4}) = (u_{2}, v_{2}, w_{2}) = (\Box, \ \Box, \ \bullet),\] \[(u_{5}, v_{5}, w_{5}) = (u_{3}, v_{3}, w_{3}) = (\Box, \ \bullet, \ \bullet).\]
Thus, if \(m = 5\), then \( _S(u_1) = _S(u_5) = 2\). In general, for each odd integer \(m \ge 7\), it follows that \( _S(u_1) = _S(u_m) = 2\), a contradiction.
Case 3. \(\{u_2, v_1, v_3\} \subseteq S\) and \(w_2 \notin S\). As shown in Figure 5(c), we saw that either \(v_2\in S\) or \(w_3\in S\) but not both. If \(v_2\in S\), then \(u_1, u_3, w_1, w_3 \notin S\). If \(w_3\in S\), then \(v_2, w_1 \notin S\) and \(u_3 \notin S\) by Lemma 3.3. This forces \(u_1 \in S\). We consider these two subcases.
Subcase 3.1. \(v_2 \in S\) and \(w_1, w_3\notin S\). Since \( _S(w_2)=2\) and \( _S(w_3)\in \{1, 2\}\), it follows that \( _S(w_3)= 1\) and so \(w_4\notin S\). Since \( _S(v_2)=3\) and \( _S(v_3)\in \{1, 2\}\), it follows that \( _S(v_3)= 2\) and so \( _S(u_3)=3\). Hence, \(u_4, v_4 \in S\). This implies that \( _S(v_4)=3\), \( _S(w_4)=2\), and \( _S(u_4)=1\). Thus, \(u_5, w_5 \notin S\) and \(v_5 \in S\). Observe that \[( _S(u_{4}), _S(v_{4}), _S(w_{4}))=( _S(u_{2}), _S(v_{2}), _S(w_{2})) = (1, 3, 2),\] \[(u_{4}, v_{4}, w_{4}) = (u_{2}, v_{2}, w_{2}) = (\bullet, \ \bullet, \ \Box),\] \[(u_{5}, v_{5}, w_{5}) = (u_{3}, v_{3}, w_{3}) = (\Box, \ \bullet, \ \Box).\]
Thus, if \(m = 5\), then \( _S(u_1) = _S(u_5) = 2\). In general, for each odd integer \(m \ge 7\), it follows that \( _S(u_1) = _S(u_m) = 2\), a contradiction.
Subcase 3.2. \(w_3 \in S\) and \(w_1, v_2\notin S\). Since \( _S(w_2)=2\) and \( _S(w_3)\in \{1, 2\}\), it follows that \( _S(w_3)= 1\) and so \(w_4\notin S\). Hence, \( _S(v_3)=2\) and \( _S(u_3)= 3\). So \(u_4\notin S\) and \(v_4 \in S\). This implies that \( _S(u_4)=2\), \( _S(v_4)=1\), and \( _S(w_4)=3\). Thus, \(u_5, w_5 \in S\) and \(v_5 \notin S\). If \(m = 5\), then \( _S(v_5)= 4\), which is impossible by Lemma 3.4. Thus, \(m \ge 7\). Then \( _S(v_5)=3\), \( _S(w_5)=2\), and \( _S(u_5)=1\). So, \(u_6, v_6 \notin S\) and \(w_6 \in S\). Then \( _S(w_6)=1\), \( _S(v_6)=2\), and \( _S(u_6)=3\). So, \(u_7, v_7 \in S\) and \(w_7 \notin S\). If \(m= 7\), then \( _S(v_1)= _S(v_7)=2\) (since \(u_1, u_7, v_1, v_7 \in S\) and \(v_2, w_1, v_6, w_7 \notin S\)), which is a contradiction. Hence, \(m \ge 9\). Then \( _S(w_7)=3\), \( _S(v_7)=1\), and \( _S(u_7)=2\). So, \(u_8 \in S\) and \(v_8, w_8 \notin S\). Next, \( _S(u_8)=1\), \( _S(w_8)=2\), and \( _S(v_8)=3\). So, \(u_9 \notin S\) and \(v_9, w_9 \in S\). Observe that \[( _S(u_{8}), _S(v_{8}), _S(w_{8}))=( _S(u_{2}), _S(v_{2}), _S(w_{2})) = (1, 3, 2),\] \[(u_{8}, v_{8}, w_{8}) = (u_{2}, v_{2}, w_{2}) = (\bullet, \ \Box, \ \Box),\] \[(u_{9}, v_{9}, w_{9}) = (u_{3}, v_{3}, w_{3}) = (\Box, \ \bullet, \ \bullet).\]
Thus, if \(m = 9\), then \( _S(v_1) = _S(v_9) = 2\), which is impossible. In general, for each odd integer \(m \ge 11\),
\(\star\) if \(m \equiv 1 \pmod 6\) or \(m \equiv 3 \pmod 6\), then \( _S(v_1)= _S(v_m)=2\) and
\(\star\) if \(m \equiv 5 \pmod 6\), then \( _S(v_m)=4\).
In each case, a contradiction is produced. ◻
Consequently, we close this section with the question: For which odd integers \(n, m \ge 5\), does the cyclical graph \(C_n \ \Box \ C_m\) possess a proper total dominating set?
In this section, we summarize results obtained on the Cartesian products of paths and cycles as well as some open problems for further study.
(I) Results on Cartesian Products of Paths and Cycles
Paths, Cycles, and Grids
\(\star\) For \(n \ge 2\), the path \(P_n\) has a proper total dominating set if and only if \(n\equiv 3 \ (\mathrm{mod}\ 4)\).
\(\star\) For \(n \ge 3\), the cycle \(C_n\) has a proper total dominating set if and only if \(n\equiv 0 \ (\mathrm{mod}\ 4)\).
\(\star\) For \(n, m \ge 2\), the grid graph \(P_n \ \Box \ P_m\) possesses a proper total dominating set.
Cylindrical graphs
\(\star\) The prism \(C_n \ \Box \ K_2\) possesses a proper total dominating set if and only if \(n\ge 4\) is even.
\(\star\) For each even integer \(n \ge 4\) and all integers \(m \ge 3\), the cylindrical graph \(C_n \ \Box \ P_m\) possesses a proper total dominating set.
\(\star\) For \(m \ge 2\), the graph \(C_3 \ \Box \ P_m\) possesses a proper total dominating set if and only if \(m = 3\).
\(\star\) Let \(n\ge 5\) be an odd integer. If \(m \ge 3\) is an integer such that \(m\equiv 3 \pmod 4\), then \(C_n \ \Box \ P_m\) has a proper total dominating set.
\(\star\) The cylindrical graph \(C_5 \ \Box \ P_4\) does not have a proper total dominating set but \(C_5 \ \Box \ P_5\) possesses a proper total dominating set.
Cyclical Graphs
\(\star\) Let \(n\) and \(m\) be integers where \(n, m \ge 3\). If at least one of \(n\) and \(m\) is even, then \(C_n \ \Box \ C_m\) has a proper total dominating set.
\(\star\) For each odd integer \(m \ge 3\), the graph \(C_3 \ \Box \ C_m\) does not possess a proper total dominating set.
(II) Problems on Cartesian Products of Paths and Cycles
\(\bullet\) Let \(n\) and \(m\) be integers where \(n \ge 5\) is odd integer and \(m \ge 6\) and \(m \not\equiv 3 \pmod 4\). Which cylindrical graphs \(C_n \ \Box \ P_m\) possess a proper total dominating set?
\(\bullet\) Let \(n\) and \(m\) be odd integers where \(n, m \ge 5\). Which cyclical graphs \(C_n \ \Box \ C_m\) possess a proper total dominating set?
In fact, there are other problems related the existence of a proper total dominating set in a Cartesian product of two graphs. For example, let \(G\) be a connected graph of order \(n \ge 3\). It is known that \(K_n\ \Box \ K_2\) does not have a proper total dominating set but \(P_n\ \Box \ K_2\) does have a proper total dominating set. Furthermore, if \(G\) is a regular bipartite graph, then \(G \ \Box \ P_2\) has a proper total dominating set (see [4]). These facts give rise to the following question.
Problem 4.1. Let \(G\) be a connected graph that may or may not have a proper total dominating set. Under what conditions, does \(G \ \Box \ K_2\) possess a proper total dominating set?
We conclude with the following more general problem.
Problem 4.2. Let \(G\) and \(H\) be connected graphs that may or may not have a proper total dominating set. Under what conditions, does \(G \ \Box \ H\) possess a proper total dominating set?
We are grateful to Professor Gary Chartrand for suggesting the concepts and problems to us and kindly providing useful information on this topic. Furthermore, we thank the anonymous referee whose valuable suggestions resulted in an improved paper.