# Domination and Independent Domination in Extended Supergrid Graphs +
## 3 NP-Completeness Results
_If_ \(u\in D^{\prime}\) _and_ \(v\
ot\in D^{\prime}\)_, then_ \(\gamma(S(u,v)-N_{G_{d}}[u])=\gamma(S(u,v)-(N_{G_{d}}[u]\cup\{v\}))=2\)_,_ \(|D^{\prime}_{[S(u,v)]}|\geqslant 3\)_, and if_ \(D^{\prime}-S(u,v)\) _does not dominate_ \(v\)_, then there exists a vertex_ \(v_{d}\) _in_ \(D^{\prime}\cap S(u,v)\) _such that_ \(v_{d}\) _dominates_ \(v\) _(see Figure_ 7b)._
3. _If_ \(u,v\
ot\in D^{\prime}\)_, then_ _if_ \((N_{G_{d}}(u)-S(u,v))\cap D^{\prime}\
eq\emptyset\) _and_ \((N_{G_{d}}(v)-S(u,v))\cap D^{\prime}\
eq\emptyset\)_, then_ \(\gamma(S(u,v)-\{u,v\})=2\) _and_ \(|D^{\prime}_{[S(u,v)]}|\geqslant 2\) _(see Figure_ 7c); otherwise,_ \(\gamma(S(u,v)-\{u,v\})=3\) _and_ \(|D^{\prime}_{[S(u,v)]}|\geqslant 3\) _(see Figure_ 7d)._  
Based on the above lemma, we prove that grid graph \(G_{g}\) contains a dominating set \(D\) with \(|D|\leqslant k\) if and only if diagonal supergrid graph \(G_{d}\) has a dominating set \(D^{\prime}\) with \(|D^{\prime}|\leqslant k+2|E(G_{g})|\). We first prove that the only if part is as follows. **Lemma 6**. : _Suppose grid graph \(G_{g}\) has a dominating set \(D\) with size \(|D|\leqslant k\). Then, diagonal supergrid graph \(G_{d}\) contains a dominating set \(D^{\prime}\) with size \(|D^{\prime}|\leqslant k+2|E(G_{g})|\)._  
Proof. : We construct a dominating set \(D^{\prime}\) of \(G_{d}\) from \(D\) such that the size of \(D^{\prime}\) is no greater than \(k+2|E(G_{g})|\). Initially, let \(D^{\prime}=D\). Let \((u,v)\) be an edge of the grid graph \(G_{g}\), and let \(S(u,v)=u\to w_{1}\to w_{2}\to w_{3}\to w_{4}\to w_{5}\to w_{6}\to v\) be the snake \((u,v)\)-path in the diagonal supergrid graph \(G_{d}\) constructed from \((u,v)\), as depicted in Figure 6(a). Consider the following three cases. Case 1: \(u,v\in D\). In this case, \(w_{1}\) and \(w_{6}\) are dominated by \(u\) and \(v\), respectively. Let \(P^{\prime}=w_{2}\to w_{3}\to w_{4}\to w_{5}\). Per Lemma 1, \(\gamma(P^{\prime})=2\). Then, \(\{w_{3},w_{5}\}\) is a minimum dominating set of \(P^{\prime}\). Let \(D^{\prime}=D^{\prime}\cup\{w_{3},w_{5}\}\). Then, \(D^{\prime}\) dominates \(V(S(u,v))\) and \(|D^{\prime}|=|D^{\prime}|+2\). Figure 6(a) shows such a dominating set of \(S(u,v)\). Case 2: either \(u\in D\) or \(v\in D\). Without loss of generality, assume that \(u\in D\) and \(v\
ot\in D\). Then, \(w_{1}\) is dominated by \(u\). Consider that \(v\) is not dominated by \(D^{\prime}\). Let \(P^{\prime}=w_{2}\to w_{3}\to w_{4}\to w_{5}\to w_{6}\to v\). Per Lemma 1, \(\gamma(P^{\prime})=2\). Then, \(\{w_{3},w_{6}\}\) is a minimum dominating set of \(P^{\prime}\). Let \(D^{\prime}=D^{\prime}\cup\{w_{3},w_{6}\}\). Then, \(D^{\prime}\) dominates \(V(S(u,v))\) and \(|D^{\prime}|=|D^{\prime}|+2\). Figure 6(b) depicts such a dominating set of \(S(u,v)\). On the other hand, consider that \(v\) is dominated by \(D^{\prime}\). Let \(P^{\prime}=w_{2}\to w_{3}\to w_{4}\to w_{5}\to w_{6}\). Per Lemma 1, \(\gamma(P^{\prime})=2\). Then, \(\{w_{3},w_{6}\}\) is a minimum dominating set of \(P^{\prime}\). Let \(D^{\prime}=D^{\prime}\cup\{w_{3},w_{6}\}\). Then, \(D^{\prime}\) dominates \(V(S(u,v))\) and \(|D^{\prime}|=|D^{\prime}|+2\). Case 3: \(u,v\
ot\in D\). Because \(D\) is a dominating set of \(G_{g}\), there exist two vertices \(z_{1}\in N_{G_{g}}(u)\) and \(z_{2}\in N_{G_{g}}(v)\) such that \(z_{1}\) and \(z_{2}\) dominate \(u\) and \(v\), respectively. Let \(S(z_{1},u)\) and \(S(z_{2},v)\) be the snake paths of \(G_{d}\) constructed from edges \((z_{1},u)\) and \((z_{2},v)\), respectively. In our construction algorithm of \(D^{\prime}\), we compute the dominating sets of \(S(z_{1},u)\) and \(S(z_{2},v)\) before the dominating set of \(S(u,v)\), where \(z_{1},z_{2}\in D\) and \(u,v\
ot\in D\). From Case 2, we can find one vertex of \(S(z_{1},u)\cap N_{G_{d}}(u)\) (respectively, \(S(z_{2},v)\cap N_{G_{d}}(v)\)) to dominate \(u\) (respectively, \(v\)) before computing the dominating set of \(S(u,v)\) (see Figure 6(b)).