# Domination and Independent Domination in Extended Supergrid Graphs +
## 3 NP-Completeness Results
By Lemma 1, there exists a set \(\{w_{2},w_{5}\}\) of \(S(u,v)-\{u,v\}\) such that it dominates \(V(S(u,v))-\{u,v\}\); see Figure 6(c). Let \(D^{\prime}=D^{\prime}\cup\{w_{2},w_{5}\}\). Then, \(D^{\prime}\) dominates \(V(S(u,v))\) and \(|D^{\prime}|=|D^{\prime}|+2\). Based on the above cases, we construct a dominating set \(D^{\prime}\) of \(G_{d}\) by the following steps. Initially, let \(D^{\prime}=D\) and let \((u,v)\in E(G_{g})\). For each \(u,v\in D\), we construct a dominating set of \(S(u,v)\) via Case 1. We then construct a dominating set of \(S(u,v)\) by Case 2 for each \(u\in D\) and \(v\
ot\in D\). Finally, for each \(u,v\
ot\in D\), a dominating set of \(S(u,v)\) is constructed via Case 3. From the above cases, \(|D^{\prime}|=|D^{\prime}|+2\) after processing each snake path of \(G_{d}\). Thus, we construct a dominating set \(D^{\prime}\) of \(G_{d}\) with size \(|D^{\prime}|=|D|+2|E(G_{g})|\leqslant k+2|E(G_{g})|\) after computing dominating sets of all snake paths in \(G_{d}\). For example, Figure 3(a) shows the dominating set \(D\) of \(G_{g}\) with \(|D|=4\), and the constructed dominating set \(D^{\prime}\) of \(G_{d}\) from \(D\) is shown in Figure 3(d), where \(|D^{\prime}|=|D|+2|E(G_{g})|=4+2\cdot 11=26\). This completes the proof of the lemma. Next, we prove that the if part is in Lemma 7. Recall that for a dominating set \(D\) of graph \(G\) and the subgraph \(H\) of \(G\), the restriction of \(D\) to \(H\) is represented as \(D_{|H}\). **Lemma 7**. : _Suppose diagonal supergrid graph \(G_{d}\) has a dominating set \(D^{\prime}\) with \(|D^{\prime}|\leqslant k+2|E(G_{g})|\). Then, grid graph \(G_{g}\) contains a dominating set \(D\) with size \(|D|\leqslant k\)._  
Proof. : We show that there exists a dominating set \(D\) of \(G_{g}\) with size \(k\) or less. To prove this lemma, we first construct a dominating set \(\hat{D}\) of \(G_{d}\) obtained from \(D^{\prime}\) such that \(|\hat{D}|\leqslant|D^{\prime}|\) and remove all vertices not in \(G_{g}\) from \(\hat{D}\), resulting in a dominating set \(D\) of \(G_{g}\). Initially, let \(\hat{D}=D^{\prime}\). Consider a snake path \(S(u,v)=u\to w_{1}\to w_{2}\to w_{3}\to w_{4}\to w_{5}\to w_{6}\to v\) of \(G_{d}\) constructed from edge \((u,v)\) of \(G_{g}\). Let \(u_{d}\) (respectively, \(v_{d}\)) be in \(D^{\prime}\) such that it dominates \(u\) (respectively, \(v\)) if \(u\
ot\in D^{\prime}\) (respectively, \(v\
ot\in D^{\prime}\)). Depending on whether \(u,v\in D^{\prime}\), we have the following three cases:Case 1: \(u,v\in D^{\prime}\). Let \(P^{\prime}=w_{2}\to w_{3}\to w_{4}\to w_{5}\). By Lemma 1, \(\gamma(P^{\prime})=2\). Let \(W=\{w_{3},w_{5}\}\) be a minimum dominating set of \(S(u,v)-(N_{G_{d}}[u]\cup N_{G_{d}}[v])\). If \(|\hat{D}|_{S(u,v)}|>4\), then let \(\hat{D}=\hat{D}-\hat{D}_{|S(u,v)}\cup W\cup\{u,v\}\), that is, \(|\hat{D}_{|S(u,v)}|=4\), after processing \(S(u,v)\) for \(u,v\in D^{\prime}\). Case 2: either \(u\in D^{\prime}\) or \(v\in D^{\prime}\). Without loss of generality, assume that \(u\in D^{\prime}\) and \(v\
ot\in D^{\prime}\). Then, \(w_{1}\) is dominated by \(u\). Let \(P^{\prime}=w_{2}\to w_{3}\to w_{4}\to w_{5}\to w_{6}\to v\). By Statement (2) of Lemma 5, at least two vertices of \(P^{\prime}\) are in \(D^{\prime}\). Let \(W=\{w_{3},w_{6}\}\) be a minimum dominating set of \(S(u,v)-N_{G_{d}}[u]\); see Figure 7b. If \(|\hat{D}|_{S(u,v)}|>3\) or \(w_{6}\
ot\in\hat{D}\), then let \(\hat{D}=\hat{D}-\hat{D}_{|S(u,v)}\cup W\cup\{u\}\), that is, \(|\hat{D}_{|S(u,v)}|=3\) in this case. In addition, \(\hat{D}\) dominates \(v\) after processing \(S(u,v)\) for \(u\in D^{\prime}\) and \(v\
ot\in D^{\prime}\). Case 3: \(u,v\
ot\in D^{\prime}\). First, consider that \(deg_{G_{g}}(u)=1\) and \(deg_{G_{g}}(v)=1\). Then, \(E(G_{g})=\{(u,v)\}\) and \(G_{d}\) only contains a snake path \(S(u,v)\). By Lemma 1, \(|D^{\prime}|\geqslant 3\). Let \(\hat{D}=\{u,w_{3},w_{6}\}\). Then, \(\hat{D}\) is a dominating set of \(G_{d}\) with size \(3\). Let \(D=\hat{D}-\{w_{3},w_{6}\}\); hence, \(D\) is a dominating set of \(G_{g}\) with size \(1\).