# Domination and Independent Domination in Extended Supergrid Graphs +
## 4 The Domination and Independent Domination Numbers of Rectangular Triangular-Supergrid Graphs
Then, there exists no minimum dominating set of \(T_{3\times k}\) containing vertex \((k,3)\), and there exists a minimum dominating set \(D_{k}\) of \(T_{3\times k}\) with size \(\left\lfloor\frac{k}{2}\right\rfloor+1\) such that \(D_{k}=\{(1+2i,2)|0\leqslant i\leqslant\left\lfloor\frac{k}{2}\right\rfloor\}\) if \(k^{\omega}2=1\); otherwise, \(D_{k}=\{(1+2i,2)|0\leqslant i\leqslant\left\lfloor\frac{k}{2}\right\rfloor-1\} \cup\{(k,2)\}\). In addition, if \(k\%2=1\), then any minimum dominating set \(\tilde{D}_{k}\) of \(T_{3\times k}\) satisfies the requirement that \(\tilde{D}_{k}\) contains vertex \((k,2)\) and does not contain vertices \((k,1)\) and \((k,3)\). Now, suppose that \(n=k+1\). There are two possible cases. Case 1: \(k\%2=1\). Let \(k=2t+1\), \(t\geqslant 1\). By induction hypothesis, any minimum dominating set \(\tilde{D}_{k}\) of \(T_{3\times k}\) does not contain vertex \((k,1)\); hence, \(\tilde{D}_{k}\) does not dominate vertex \((k+1,1)\). Thus, \(\gamma(T_{3\times(k+1)})>\gamma(T_{3\times k})\). Let \(D_{k+1}=D_{k}\cup\{(k+1,2)\}\). Then, \(|D_{k+1}|=|D_{k}|+1=t+2\); hence, \(D_{k+1}\) is a minimum dominating set of \(T_{3\times(k+1)}\). Therefore, Claim (C1) holds true in this case. Next, we verify Claim (C2). Let \(u=(k,1)\), \(v=(k+1,2)\), and let \(w=(k+1,1)\). Assume by contradiction that \(\tilde{D}\) is a minimum domination set of \(T_{3\times(k+1)}\) satisfying the requirement that \(\tilde{D}\) contain vertex \((k+1,3)\). To dominate \(w\), one of \(u,v,w\) must be in \(\tilde{D}\). Consider that \(u\in\tilde{D}\). Then, \(|\tilde{D}_{|T_{3\times k}|}>\gamma(T_{3\times k})\) by induction hypothesis. Then, \(\tilde{D}=\tilde{D}_{|T_{3\times k}|}\cup\{(k+1,3)\}\); hence, \(|\tilde{D}|>\gamma(T_{3\times k})+1\). Thus, \(|\tilde{D}|\geqslant\gamma(T_{3\times k})+2\). This contradicts our above construction \(D_{k+1}\) of \(T_{3\times(k+1)}\) with size \(|D_{k+1}|=\gamma(T_{3\times k})+1=t+2\). In addition, consider that \(w\) or \(v\) is in \(\tilde{D}\). Then, \(\tilde{D}_{|T_{3\times(k-1)}}\cup\{v,(k+1,3)\}\subseteq\tilde{D}\); hence, \(|\tilde{D}|\geqslant|\tilde{D}_{|T_{3\times(k-1)}|}+2\). By induction hypothesis, \(|\tilde{D}_{|T_{3\times(k-1)}|}\geqslant|D_{k-1}|=\left\lfloor\frac{k-1}{2} \right\rfloor+1=\left\lfloor\frac{2t}{2}\right\rfloor+1=t+1\). Then, \(|\tilde{D}|\geqslant|\tilde{D}|T_{3\times(k-1)}|+2\geqslant t+3\). Thus, \(|\tilde{D}|>|D_{k+1}|\), where \(|D_{k+1}|=t+2\) and \(D_{k+1}\) is a dominating set of \(T_{3\times(k+1)}\); hence, a contradiction occurs. By contradiction, there exists no minimum domination set of \(T_{3\times(k+1)}\) containing vertex \((k+1,3)\). Thus, Claim (C2) holds true when \(n=k+1\). Case 2: \(k\%2=0\). In this case, let \(D_{k+1}=D_{k}-\{(k,1)\}\cup\{(k+1,2)\}\). Then, \(|D_{k+1}|=|D_{k}|=\left\lfloor\frac{k}{2}\right\rfloor+1\). Because \(T_{3\times k}\) is a subgraph of \(T_{3\times(k+1)}\), \(\gamma(T_{3\times k})\leqslant\gamma(T_{3\times(k+1)})\), it is true that \(D_{k+1}\) is a minimum dominating set of \(T_{3\times(k+1)}\). Thus, Claim (C1) holds true in this case. Next, we verify Claim (C2) in this case. By similar arguments to those proving Case 1, we can verify that there exists no minimum domination set of \(T_{3\times(k+1)}\) containing vertices \((k+1,1)\) and \((k+1,3)\). Let \(z=(k+1,2)\), \(z_{1}=(k,1)\), \(z_{2}=(k,2)\), \(z_{3}=(k,3)\), and let \(Z=\{z_{1},z_{2},z_{3}\}\), as shown in Figure 12. Assume by contradiction that there exists a minimum domination set \(\tilde{D}\) of \(T_{3\times(k+1)}\) such that \(z\
ot\in\tilde{D}\). To dominate \((k+1,1)\) and \((k+1,3)\), at least two vertices of \(Z\) are necessary. If \(z_{3}\in\tilde{D}\), then \(\tilde{D}\) is not a minimum dominating set of \(T_{3\times k}\); by induction hypothesis, a contradiction occurs. Thus, \(z_{1},z_{2}\in\tilde{D}\). Let \(\tilde{D}^{\prime}=\tilde{D}-\{(k,1)\}\).