# Domination and Independent Domination in Extended Supergrid Graphs +
## 3 NP-Completeness Results
: _Given a grid graph \(G_{g}\), Algorithm 1 constructs a diagonal supergrid graph \(G_{d}\) in \(O(|V(G_{g})|+|E(G_{g})|)\)-linear time._  
Next, we verify that grid graph \(G_{g}\) has a dominating set \(D\) of size \(|D|\leqslant k\) if and only if diagonal supergrid graph \(G_{d}\) contains a dominating set \(D^{\prime}\) of size \(|D^{\prime}|\leqslant k+2|E(G_{g})|\). Before providing the proof, we first observe several properties of the snake path. Note that the snake path is a simple path \(P_{8}\) with eight vertices. Recall that for a dominating set \(D\) of graph \(G\) and the subgraph \(H\) of \(G\), we denote the restriction from \(D\) to \(H\) as \(D_{|H}\). Let \(D^{\prime}\) be a dominating set of diagonal supergrid graph \(G_{d}\), and let \(S(u,v)\) be a snake path with connectors \(u\) and \(v\) in \(G_{d}\). Let \(u_{d}\in N_{G_{d}}(u)\cap D^{\prime}\) if \(u\
ot\in D^{\prime}\), and \(v_{d}\in N_{G_{d}}(v)\cap D^{\prime}\) if \(v\
ot\in D^{\prime}\). Then, \(u_{d}\) and \(v_{d}\) dominate \(u\) and \(v\), respectively, if \(u,v\
ot\in D^{\prime}\). According to whether \(u\) and \(v\) are in \(D^{\prime}\), we consider the following situations. Case 1: \(u,v\in D^{\prime}\). Because \(D^{\prime}\) is a dominating set of \(G_{d}\), \(G_{d}[S(u,v)-(N_{G_{d}}[u]\cup N_{G_{d}}[v])]\) is a path \(P_{4}\) with four vertices. Per Lemma 1, \(\gamma(S(u,v)-(N_{G_{d}}[u]\cup N_{G_{d}}[v]))=2\) (see Figure 7a). Therefore, \(|D^{\prime}_{[S(u,v)-\{u,v\}]}\geqslant 2\) and \(\gamma(S(u,v)-(N_{G_{d}}[u]\cup N_{G_{d}}[v]))=2\). Case 2: either \(u\in D^{\prime}\) or \(v\in D^{\prime}\). Without loss of generality, assume \(u\in D^{\prime}\) and \(v\
ot\in D^{\prime}\). Consider that \(S(u,v)\) does not contain \(v_{d}\). Then, \(G_{d}[S(u,v)-(N_{G_{d}}[u]\cup\{v\})]\) is a path \(P_{5}\) with five vertices. Per Lemma 1, \(\gamma(S(u,v)-(N_{G_{d}}[u]\cup\{v\}))=2\). On the other hand, Consider that \(S(u,v)\) contains \(v_{d}\). Then, \(G_{d}[S(u,v)-N_{G_{d}}[u]]\) is a path \(P_{6}\) with six vertices. Per Lemma 1, \(\gamma(S(u,v)-N_{G_{d}}[u])=2\) (see Figure 7b). In any case, \(\gamma(S(u,v)-(N_{G_{d}}[u]\cup\{v\})=\gamma(S(u,v)-N_{G_{d}}[u]))=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\). Case 3: \(u,v\
ot\in D^{\prime}\). Depending on the positions of \(u_{d}\) and \(v_{d}\), we have the following three subcases. Case 3: \(u_{d},v_{d}\
ot\in S(u,v)\). In this subcase, \(\{u_{d},v_{d}\}\cap S(u,v)=\emptyset\). Then, \(S(u,v)-\{u,v\}\) is a path \(P_{6}\) with six vertices. Per Lemma 1, \(\gamma(S(u,v)-\{u,v\})=2\) (see Figure 7c). Thus, \(|D^{\prime}_{[S(u,v)]}\geqslant 2\). Case 3: either \(u_{d}\
ot\in S(u,v)\) or \(v_{d}\
ot\in S(u,v)\). Without loss of generality, assume that \(u_{d}\in S(u,v)\) and \(v_{d}\
ot\in S(u,v)\). Then, \(S(u,v)-(N_{G_{d}}(u_{d})\cup\{v\})\) is a path \(P_{4}\) with four vertices. Per Lemma 1, \(\gamma(S(u,v)-(N_{G_{d}}(u_{d})\cup\{v\}))=2\) (see Figure 7d). Thus, \(|D^{\prime}_{[S(u,v)-(N_{G_{d}}(u_{d})\cup\{v\})]}\geqslant 2\) and \(|D^{\prime}_{[S(u,v)]}\geqslant 3\). Then, \(\gamma(S(u,v)-\{u,v\})=3\). Case 3: \(u_{d},v_{d}\in S(u,v)\). In this subcase, it needs at least one other vertex of \(S(u,v)\) to dominate \(S(u,v)-(N_{G_{d}}(u_{d})\cup N_{G_{d}}(v_{d}))\). Thus, \(|D^{\prime}_{[S(u,v)]}\geqslant 3\) and \(\gamma(S(u,v))=3\). It follows from the above cases that we can conclude the following lemma. Lemma 5: _Let \(D^{\prime}\) be a dominating set of diagonal supergrid graph \(G_{d}\) constructed by Algorithm 1, and let \(S(u,v)\) be a snake path with connectors \(u\) and \(v\) in \(G_{d}\). Then, the following statement holds:_  
1. _If_ \(u,v\in D^{\prime}\)_, then_ \(\gamma(S(u,v)-(N_{G_{d}}[u]\cup N_{G_{d}}[v]))=2\) _and_ \(|D^{\prime}_{[S(u,v)-\{u,v\}]}|\geqslant 2\) _(see Figure_ 7a)._
2.