# Domination and Independent Domination in Extended Supergrid Graphs +
## 3 NP-Completeness Results
For example, given a dominating set \(D^{\prime}\) of \(G_{d}\) with size 22 in Figure 9a, the constructed dominating set \(\hat{D}\) of \(G_{d}\) with size 22 from \(D^{\prime}\) is depicted in Figure 9b. Then, \(\hat{D}\) satisfies the following properties:  
1. \(|\hat{D}|\leqslant|D^{\prime}|\),
2. for each snake \((u,v)\)-path \(S(u,v)\), \(|\hat{D}\cap(S(u,v)-\{u,v\})|=2\), and
3. for each snake \((u,v)\)-path \(S(u,v)\) with \(u,v\
ot\in\hat{D}\), there exist \(z_{1}\in N_{G_{g}}(u)\) and \(z_{2}\in N_{G_{g}}(v)\) such that \(z_{1},z_{2}\in\hat{D}\) while \(deg_{G_{g}}(u)\
eq 1\) and \(deg_{G_{g}}(v)\
eq 1\). Then, a dominating set \(D\) of \(G_{g}\) is obtained from \(\hat{D}\) according to the following steps:  
1. initially, let \(D=\hat{D}\);
2. remove from \(D\) all vertices of \(D\) that are not in \(D_{g}\);
3. the result set \(D\) is a dominating set of \(G_{g}\). Because for each snake path \(S(u,v)\), \(\hat{D}\cap S(u,v)\) contains exactly two vertices that are not in \(G_{g}\), we obtain \(|D|=|\hat{D}|-2|E(G_{g})|\). Then, \(|D|=|\hat{D}|-2|E(G_{g})|\leqslant|D^{\prime}|-2|E(G_{g})|\leqslant(k+2|E(G_{ g})|)-2|E(G_{g})|=k\). Therefore, we construct a dominating set \(D\) of \(G_{g}\) of size \(|D|\leqslant k\). It immediately follows from Lemmas 6 and 7 that the following lemma is summarized:  
Lemma 8: _Let \(G_{g}\) be a grid graph, and let \(G_{d}\) be a diagonal supergrid graph constructed from \(G_{g}\) by Algorithm 1. Then, \(G_{g}\) has a dominating set \(D\) with size \(|D|\leqslant k\) if and only if \(G_{d}\) contains a dominating set \(D^{\prime}\) with size \(|D^{\prime}|\leqslant k+2|E(G_{g})|\)._  
Obviously, the domination problem on a diagonal supergrid graph is in NP. By Theorem 1 and Lemmas 4 and 8 we derive the following theorem:  
Figure 9: (**a**) The dominating set \(D^{\prime}\) of \(G_{d}\) with size 22, and (**b**) a dominating set \(\hat{D}\) of \(G_{d}\) with size 22 (\(\leqslant|D^{\prime}|\)) obtained from \(D^{\prime}\). Solid lines indicate the edges of \(G_{d}\), double circles represent the vertices of \(G_{g}\), and filled circles indicate the vertices in a dominating set of \(G_{d}\). **Theorem 2**. : _The domination problem for diagonal supergrid graphs is NP-complete._  
The dominating sets of diagonal supergrid graphs constructed in Lemmas 6 and 7 can be easily modified to be independent dominating sets. Therefore, the independent domination problem on diagonal supergrid graphs is NP-complete as well, and the following corollary holds true. **Corollary 1**. : _The independent domination problem for diagonal supergrid graphs is NP-complete._  
Through the construction of diagonal supergrid graph \(G_{d}\), we can see that \(G_{d}\) is a supergrid graph which is a vertex-induced subgraph of the infinite two-dimensional supergrid \(S^{\infty}\). Therefore, the following theorem holds immediately. **Theorem 3**. : _The domination and independent domination problems for supergrid graphs are NP-complete._  
The NP-complete results above can be easily extended to triangular supergrid graphs. Recall that a triangular supergrid graph is an extended supergrid graph of which the edge set contains at least one \(r\)-skewed diagonal edge and does not contain any \(l\)-skewed diagonal edges. To verify that the domination problem on a triangular supergrid graph is NP-complete, we modify Algorithm 1 as follows:  
1. enlarge the input grid graph \(G_{g}\) to another grid graph \(G^{\prime}_{g}\) such that each edge of \(G_{g}\) is transformed into a horizontal or vertical path with six edges (see Figure 10b);
2. for each horizontal (respectively, vertical) \((u,v)\)-path in \(G^{\prime}_{g}\) where \(u,v\in V(G_{g})\), replace it by a horizontal (respectively, vertical) triangle path \(T(u,v)\) connecting \(u\) and \(v\) (see Figure 10c);
3. the constructed graph is a triangular supergrid graph \(G_{\tau}\) (see Figure 10d), and outputs \(G_{\tau}\).