# Domination and Independent Domination in Extended Supergrid Graphs +
## 4 The Domination and Independent Domination Numbers of Rectangular Triangular-Supergrid Graphs  
In this section, we first compute \(\gamma(T_{m\times n})=\gamma_{\text{ind}}(T_{m\times n})\) for a rectangular triangular-supergrid graph \(T_{n\times n}\) with \(n\geqslant m\) and \(3\geqslant m\geqslant 2\). We then provide an upper bound of \(\gamma(T_{m\times n})\) and \(\gamma_{\text{ind}}(T_{m\times n})\) for \(n\geqslant m\geqslant 4\). First, we consider \(n\geqslant m\) and \(m=2\), as follows. Lemma 9: \(\gamma(T_{2\times n})=\gamma_{\text{ind}}(T_{2\times n})=\lceil\frac{2n}{5}\rceil\)_._  
Proof: Through the structure of \(T_{2\times n}\), a vertex of \(T_{2\times n}\) dominates at most five vertices, including its four neighbors and itself. Thus, \(\gamma(T_{2\times n})\geqslant\lceil\frac{2n}{5}\rceil\). We compute a dominating set of \(T_{2\times n}\) with size \(\lceil\frac{2n}{5}\rceil\), as follows. First, we make \(\lfloor\frac{n}{5}\rfloor\) or \(\lfloor\frac{n}{5}\rfloor-1\) vertical separations on \(T_{2\times n}\) to obtain \(\lceil\frac{n}{5}\rceil\) subgraphs \(T_{1}\), \(T_{2}\), \(\ldots\), \(T_{\lfloor\frac{n}{5}\rfloor}\), \(\mathsf{T}^{*}\) of \(T_{2\times n}\) such that \(T_{i}\), \(1\leqslant i\leqslant\lfloor\frac{n}{5}\rfloor\) is a rectangular triangular-supergrid graph \(T_{2\times 5}\) and \(\mathsf{T}^{*}\) is a \(T_{2\times j}\), \(1\leqslant j\leqslant 4\), if \(n\%5\
eq 0\). Note that \(\mathsf{T}^{*}=\emptyset\) when \(n\%5=0\). Let \(\mu_{i}=(2,2)\) and \(v_{i}=(4,1)\) be two vertices of \(T_{i}\) for \(1\leqslant i\leqslant\lfloor\frac{n}{5}\rfloor\), and let \(D^{\prime}=\cup_{1\leqslant i\leqslant\lfloor\frac{n}{5}\rfloor}\{\mu,v_{i}\}\). Then, \(D^{\prime}\) is a dominating set of \(T_{2\times n}-\mathsf{T}^{*}\). Consider that \(\mathsf{T}^{*}\) does exist, i.e., \(n\%5\
eq 0\). Then, \(\mathsf{T}^{*}=T_{2\times j}\) for \(1\leqslant j\leqslant 4\). We then compute one or two vertices \(\mu\) and \(\
u\) of \(\mathsf{T}^{*}\) as follows: if \(j=1\), let \(\mu=(1,2)\); otherwise, if \(j=2\), let \(\mu=(2,2)\). Furthermore, if \(j=3\), let \(\mu=(2,2)\) and \(\
u=(3,1)\); otherwise, if \(j=4\), let \(\mu=(2,2)\) and \(\
u=(4,2)\). Then, \(\{\mu,\
u\}\) dominates \(\mathsf{T}^{*}\). Let \(D=D^{\prime}\cup\{\mu,\
u\}\). Then, \(|D|=\lceil\frac{2n}{5}\rceil\) and \(D\) dominates \(T_{2\times n}\). Thus, \(\gamma(T_{2\times n})=\lceil\frac{2n}{5}\rceil\). By the above construction, we can see that \(D\) is an independent dominating set of \(T_{2\times n}\); hence, \(\gamma_{\text{ind}}(T_{2\times n})=\lceil\frac{2n}{5}\rceil\). For instance, Figure 11 depicts our constructed (independent) dominating set of \(T_{2\times n}\) for \(2\leqslant n\leqslant 10\). Next, we compute \(\gamma(T_{3\times n})\) and \(\gamma_{\text{ind}}(T_{3\times n})\) as the following lemma. Lemma 10: \(\gamma(T_{3\times n})=\gamma_{\text{ind}}(T_{3\times n})=\lfloor\frac{n}{2} \rfloor+1\)_._  
Proof: We first claim the following:  
1. There exists a minimum dominating set \(D_{n}\) of \(T_{3\times n}\) with size \(\lfloor\frac{n}{2}\rfloor+1\) such that \(D_{n}=\{(1+2i,2)|0\leqslant i\leqslant\lfloor\frac{n}{2}\rfloor\}\) if \(n\%2=1\); otherwise, \(D_{n}=\{(1+2i,2)|0\leqslant i\leqslant\lfloor\frac{n}{2}\rfloor-1\}\cup\{(n,2)\}\). 2. For any minimum dominating set \(\hat{D}_{n}\) of \(T_{3\times n}\), \(\hat{D}\) does not contain vertex \((n,3)\), and if \(n\%2=1\), then \(\hat{D}\) contains vertex \((n,2)\) and does not contain vertex \((n,1)\). We prove the above claims by induction on \(n\), where \(n\geqslant 3\). Initially, let \(n=3\), \(4\), or \(5\). By inspecting \(T_{3\times 3}\), \(T_{3\times 4}\), and \(T_{3\times 5}\), it is easy to verify that the above claims hold true; see Figure 12. Assume that the claims hold when \(n=k\) and \(k\geqslant 5\).