# Domination and Independent Domination in Extended Supergrid Graphs +
## 4 The Domination and Independent Domination Numbers of Rectangular Triangular-Supergrid Graphs
Then, \(\tilde{D}^{\prime}\) remains a dominating set of \(T_{3\times k}\), as \(N_{T_{3\times k}}[z_{1}]\subset N_{T_{3\times k}}(z_{2})\); that is, \(\tilde{D}\) is not a minimum dominating set of \(T_{3\times k}\). Thus, \(|\tilde{D}|>\gamma(T_{3\times k})\). This contradicts the requirement that \(D_{k+1}\) constructed above be a dominating set of \(T_{3\times(k+1)}\) with size \(\gamma(T_{3\times k})\). Thus, any minimum domination set of \(T_{3\times(k+1)}\) contains vertex \(z=(k+1,2)\). It follows from the above arguments that Claim (C2) holds true when \(n=k+1\). By the above cases, Claims (C1) and (C2) hold true when \(n=k+1\). By induction, these claims hold true for \(n\geqslant 3\). Thus, \(\gamma(T_{3\times n})=\left\lfloor\frac{n}{2}\right\rfloor+1\). Figure 12 shows the minimum dominating set \(D_{n}\) of \(T_{3\times n}\) for \(3\leqslant n\leqslant 10\). Because each independent dominating set of a graph is a dominating set for that graph, \(\gamma(T_{3\times n})\leqslant\gamma_{\text{ind}}(T_{3\times n})\). For the case of \(n\%2=1\), \(D_{n}\) in Claim (C1) is an independent set as well; hence, it is a minimum independent dominating set of \(T_{3\times n}\). Consider \(n\%2=0\). Let \(D^{\prime}_{n}=D_{n}-\{(n,2)\}\cup\{(n,1)\}\). Then, \(|D^{\prime}_{n}|=|D_{n}|\) and \(D^{\prime}_{n}\) is an independent set Next, we consider \(n\geqslant m\geqslant 4\) for a rectangular triangular-supergrid graph \(T_{m\times n}\). Lemma 11: _Let \(T_{m\times n}\) be a rectangular triangular-supergrid graph with \(n\geqslant m\geqslant 4\). Then, \(\gamma(T_{m\times n})\leqslant\lceil\frac{m}{3}\rceil\lceil\frac{n+1}{2}\rceil\) and \(\gamma_{\text{ind}}(T_{m\times n})\leqslant\lceil\frac{m}{3}\rceil\lceil\frac {n+1}{2}\rceil\)._  
Proof: Based on Lemmas 1, 9 and 10, we compute an (independent) dominating set of \(T_{m\times n}\) as follows. First, we make \(\lfloor\frac{m}{3}\rfloor-1\) or \(\lfloor\frac{m}{3}\rfloor\) horizontal separations on \(T_{m\times n}\) to obtain \(\lfloor\frac{m}{3}\rfloor\) disjoint subgraphs \(T_{3\times n}\) and one \(T_{(m-3\cdot\lfloor\frac{m}{3}\rfloor)\times n}\) if \(m\%3\
eq 0\), as shown in Figure 13a. Let \(\mathbb{T}_{1}\), \(\mathbb{T}_{2}\), \(\cdots\), \(\mathbb{T}_{\lceil\frac{m}{3}\rceil}\) be partitioned subgraphs such that \(\mathbb{T}_{i}\) is located above \(\mathbb{T}_{i+1}\) for \(1\leqslant i\leqslant\lceil\frac{m}{3}\rceil-1\). By Lemma 10, we can obtain a minimum (independent) dominating set \(D_{i}\) of \(\mathbb{T}_{i}\) with size \(\lfloor\frac{n}{2}\rfloor+1\) for \(1\leqslant i\leqslant\lceil\frac{m}{3}\rceil-1\). Depending on the number of \(m\%3\), we consider the following cases:  
Case 1: \(m\%3=0\). In this case, let \(D_{\lceil\frac{m}{3}\rceil}\) be the minimum (independent) dominating set of \(\mathbb{T}_{\lceil\frac{m}{3}\rceil}\) constructed from the proof of Lemma 10, and let \(D=\cup_{1\leqslant i\leqslant\lceil\frac{m}{3}\rceil}D_{i}\). Then, \(|D|=\lceil\frac{m}{3}\rceil(\lfloor\frac{n}{2}\rfloor+1)\). Case 2: \(m\%3=1\). In this case, let \(D_{\lfloor\frac{m}{3}\rceil}\) be the minimum (independent) dominating set of \(\mathbb{T}_{\lceil\frac{m}{3}\rceil}\) constructed from Lemma 11. Then, \(|D_{\lceil\frac{m}{3}\rceil}|=\lceil\frac{n}{3}\rceil\). Let \(D=\cup_{1\leqslant i\leqslant\lceil\frac{m}{3}\rceil-1}D_{i}\cup D_{\lceil \frac{m}{3}\rceil}\). Then, \(|D|=(\lceil\frac{m}{3}\rceil-1)(\lfloor\frac{n}{2}\rfloor+1)+\lceil\frac{n}{ 3}\rceil\leqslant\lceil\frac{m}{3}\rceil(\lfloor\frac{n}{2}\rfloor+1)\). Case 3: \(m\%3=2\). In this case, let \(D_{\lceil\frac{m}{3}\rceil}\) be the minimum (independent) dominating set of \(\mathbb{T}_{\lceil\frac{m}{3}\rceil}\) constructed from the proof of Lemma 9. Then, \(|D_{\lceil\frac{m}{3}\rceil}|=\lceil\frac{2m}{5}\rceil\). Let \(D=\cup_{1\leqslant i\leqslant\lceil\frac{m}{3}\rceil-1}D_{i}\cup D_{\lceil \frac{m}{3}\rceil}\). Then, \(|D|=(\lceil\frac{m}{3}\rceil-1)(\lfloor\frac{n}{2}\rfloor+1)+\lceil\frac{2n}{ 5}\rceil\leqslant\lceil\frac{m}{3}\rceil(\lfloor\frac{n}{2}\rfloor+1)\).