# Domination and Independent Domination in Extended Supergrid Graphs +
## 3 NP-Completeness Results
Therefore,  
Figure 4: (**a**) A grid graph \(G_{g}\), (**b**) a grid graph \(G_{g}^{\prime}\) that magnifies each edge of \(G_{g}\) by a factor of seven, (**c**) a snake \((u,v)\)-path \(S(u,v)\) with eight vertices, and (**d**) a diagonal supergrid graph \(G_{d}\) constructed from \(G_{g}^{\prime}\) by replacing each enlarged path with a snake path in (**e**), where the solid lines represent edges of \(G_{g}\) and \(G_{d}\), double circles represent the vertices of \(G_{g}\), and filled circles represent the vertices in a dominating set of \(G_{g}\) or \(G_{d}\). none of the vertices are repeated except for the connectors of the snake paths. Algorithm 1 illustrates the detailed steps above for placing snake paths. For example, Figure 6 describes the arrangement of snake paths in \(G_{d}\) for \(G_{g}=G_{16\times 16}\). Then, the following property holds immediately. **Lemma 3**. : _Algorithm 1 arranges the snake paths of \(G_{d}\) such that these paths are vertex-disjoint except for their connectors._  
The construction algorithm of diagonal supergrid graph \(G_{d}\) is formally presented as Algorithm 1. Because a snake path is a diagonal supergrid graph and the input grid graph \(G_{g}\) contains at least one edge, the constructed graph \(G_{d}\) of Algorithm 1 is a diagonal supergrid graph. In addition, each edge of \(G_{g}\) is enlarged a constant number of times, and each enlarged edge is replaced with one snake path, Algorithm 1 runs in \(O(|V(G_{g})|+|E(G_{g})|)\)-linear time. Thus, the following lemma holds true. Figure 5: Arrangement of snake paths for a square \((i,j)\), \((i,j+1)\), \((i+1,j)\), \((i+1,j+1)\) of \(G_{g}\), where (a) \(i,j\) are even or odd and (b) \(i\) is odd and \(j\) is even, or \(i\) is even and \(j\) is odd. Figure 6: Arrangement of snake paths in \(G_{d}\) from \(G_{g}=G_{16\times 16}\); thick triangle lines denote the snake paths of \(G_{d}\) and horizontal or vertical dashed lines represent the enlarged paths of \(G_{g}^{\prime}\). ```
Input: A grid graph \(G_{g}\). (see Figure 4a) Output: A diagonal supergrid graph \(G_{d}\). (see Figure 4d) Method: // an algorithm for constructing a diagonal supergrid graph from a grid graph
1. enlarge \(G_{g}\) to a grid graph \(G^{\prime}_{g}\), so that each edge of \(G_{g}\) is transformed into a vertical or horizontal path with 7 edges; (see Figure 4b)
2. let \(G_{d}=G^{\prime}_{g}\);
3.for each enlarged \((u,v)\)-path \(P(u,v)\) in \(G^{\prime}_{g}\), where \(u,v\in V(G_{g})\)do
4. let \(u=(u_{x},u_{y})\) and \(v=(v_{x},v_{y})\) be the vertices in grid graph \(G_{g}\) with \(u_{x}\leqslant v_{x}\) and \(u_{y}\leqslant v_{y}\);
5. let \(S(u,v)\) be the snake \((u,v)\)-path corresponding to \(P(u,v)\); // Note that if \(v_{x}=u_{x}+1\), then \(P(u,v)\) is a horizontal path; otherwise, \(P(u,v)\) is a vertical path
6.if\(v_{x}=u_{x}+1\)then
7.if\(u_{y}\%2=1\)then
8.if\(u_{x}\%2=1\)then
9. replace \(P(u,v)\) with \(S(u,v)\) in \(G_{d}\) so that \(S(u,v)\) is above \(P(u,v)\);
10.else
11. replace \(P(u,v)\) with \(S(u,v)\) in \(G_{d}\) so that \(S(u,v)\) is below \(P(u,v)\);
12.else
13.if\(u_{x}\%2=1\)then
14. replace \(P(u,v)\) with \(S(u,v)\) in \(G_{d}\) so that \(S(u,v)\) is below \(P(u,v)\);
15.else
16. replace \(P(u,v)\) with \(S(u,v)\) in \(G_{d}\) so that \(S(u,v)\) is above \(P(u,v)\);
17.else
18.if\(u_{x}\%2=1\)then
19.if\(u_{y}\%2=1\)then
20. replace \(P(u,v)\) with \(S(u,v)\) in \(G_{d}\) so that \(S(u,v)\) is to the right of \(P(u,v)\);
21.else
22. replace \(P(u,v)\) with \(S(u,v)\) in \(G_{d}\) so that \(S(u,v)\) is to the left of \(P(u,v)\);
23.else
24.if\(u_{y}\%2=1\)then
25. replace \(P(u,v)\) with \(S(u,v)\) in \(G_{d}\) so that \(S(u,v)\) is to the left of \(P(u,v)\);
26.else
27. replace \(P(u,v)\) with \(S(u,v)\) in \(G_{d}\) so that \(S(u,v)\) is to the right of \(P(u,v)\);
28. ```  
**Algorithm 1**The diagonal supergrid graph construction algorithm  
**Lemma 4**.