# Domination and Independent Domination in Extended Supergrid Graphs +
## 3 NP-Completeness Results
Then, \(3\leqslant|D^{\prime}|\leqslant k+2\cdot 1\), and hence \(|D|=1\leqslant k\). Thus, the lemma holds when \(u,v\
ot\in D^{\prime}\) and \(deg_{G_{g}}(u)=deg_{G_{g}}(v)=1\). In the following, suppose that \(deg_{G_{g}}(u)\
eq 1\) or \(deg_{G_{g}}(v)\
eq 1\). Then, there exists at least one vertex \(z_{1}\) of \(G_{g}\) such that \(z_{1}\in N_{G_{g}}(u)\) or \(z_{1}\in N_{G_{g}}(v)\). Without loss of generality, assume that \((z_{1},u)\in E(G_{g})\). We pick \(z_{1}\) to satisfy the requirement that if \(z_{1}\
ot\in D^{\prime}\), then \(N_{G_{g}}(u)\cap D^{\prime}=\emptyset\). Let \(S(z_{1},u)=z_{1}\to x_{1}\to x_{2}\to x_{3}\to x_{4}\to x_{5}\to x_{6}\to u\) be the snake path of \(G_{d}\) constructed from edge \((z_{1},u)\) of \(G_{g}\), as shown in Figure 8a. Depending on whether \(z_{1}\in D^{\prime}\), there are two subcases. Case 3.1: \(z_{1}\
ot\in D^{\prime}\). In this subcase, \(N_{G_{g}}(u)\cap D^{\prime}=\emptyset\). Suppose that \(u_{d}\in S(u,v)\). By Statement (3) of Lemma 5, \(|D^{\prime}_{|S(u,v)}|\geqslant 3\). Let \(\hat{D}=\hat{D}-D^{\prime}_{|S(u,v)}\cup\{u,w_{3},w_{6}\}\). Then, the size of \(\hat{D}\) does not increase and \(u\in\hat{D}\). On the other hand, suppose that \(u_{d}\in S(z_{1},u)\). By Statement (3) of Lemma 5, \(|D^{\prime}_{|S(z_{1},u)}|\geqslant 3\). Let \(\hat{D}=\hat{D}-D^{\prime}_{|S(z_{1},u)}\cup\{u,x_{1},x_{4}\}\). Then, the size of \(\hat{D}\) does not increase and \(u\in\hat{D}\). In any case, we can set \(u\in\hat{D}\) and \(|\hat{D}|\) does not increase. Then, it is the same as Case 2. Figure 8a depicts such a case. Case 3.2: \(z_{1}\in D^{\prime}\). In this subcase, \(\gamma(S(z_{1},u))=3\) and \(\{z_{1},x_{3},x_{6}\}\) is a minimum dominating set of \(S(z_{1},u)\); see Figure 8b,c. If \(|D^{\prime}_{|S(z_{1},u)|}>3\) or \(x_{6}\
ot\in D^{\prime}\), let \(\hat{D}=\hat{D}-D^{\prime}_{|S(z_{1},u)}\cup\{z_{1},x_{3},x_{6}\}\). Depending on whether \(deg_{G_{g}}(v)=1\), we consider the following subcases. Case 3.2.1: \(deg_{G_{g}}(v)\
eq 1\). In this subcase, there exists a vertex \(z_{2}\) of \(N_{G_{g}}(v)\). We pick such a vertex \(z_{2}\), which is the same as that of \(z_{1}\). Let \(S(z_{2},v)=z_{2}\to y_{1}\to y_{2}\to y_{3}\to y_{4}\to y_{5}\to y_{6}\to v\) be the snake path of \(G_{d}\) constructed from edge \((z_{2},v)\) of \(G_{g}\), as shown in Figure 8b. If \(z_{2}\
ot\in D^{\prime}\), then it is the same as Case 3.1. Consider that \(z_{2}\in D^{\prime}\). Then, \(\{z_{2},y_{3},y_{6}\}\) is a minimum dominating set of \(S(z_{2},v)\) and \(v\) is dominated by \(y_{6}\). If \(|D^{\prime}_{|S(z_{2},v)|}>3\) or \(y_{6}\
ot\in D^{\prime}\), then let \(\hat{D}=\hat{D}-D^{\prime}_{|S(z_{2},v)}\cup\{z_{2},y_{3},y_{6}\}\). In addition, \(u\) and \(v\) are dominated by \(\hat{D}\) after processing \(S(z_{1},u)\) and \(S(z_{2},v)\). By Statement (3) of Lemma 5, \(\gamma(S(u,v)-\{u,v\})=2\). Let \(\{w_{2},w_{5}\}\) be a minimum dominating set of \(S(u,v)-\{u,v\}\). If \(|D^{\prime}_{|S(u,v)}|>2\), then let \(\hat{D}=\hat{D}-D^{\prime}_{|S(u,v)}\cup\{w_{2},w_{5}\}\). Figure 8b depicts a such construction of \(\hat{D}\). Case 3.2.2: \(deg_{G_{g}}(v)=1\). In this subcase, \(w_{6}\) dominates \(v\); see Figure 8c. By Statement (3) of Lemma 5, \(|D^{\prime}_{|S(u,v)|}\geqslant 3\). We then set \(u\) to be in \(\hat{D}\) and re-compute the minimum dominating set of \(S(u,v)\), that is, \(\hat{D}=\hat{D}-D^{\prime}_{|S(u,v)}\cup\{u,w_{3},w_{6}\}\). Then, \(|\hat{D}|\) does not increase and \(u\in\hat{D}\). Figure 8c shows a such minimum dominating set of \(S(z_{1},u)\cup S(u,v)\) in this subcase. From the above cases, we can construct a dominating set \(\hat{D}\) of \(G_{d}\) from \(D^{\prime}\) such that \(|\hat{D}|\leqslant|D^{\prime}|\), as follows. First, for each \(u,v\
ot\in D^{\prime}\) we construct dominating sets of \(S(u,v)\) via Case 3. Then, for each \(u\in D^{\prime}\) and \(v\
ot\in D^{\prime}\) we construct dominating sets of \(S(u,v)\) via Case 2. Finally, we construct dominating sets of \(S(u,v)\) via Case 1 for \(u,v\in D^{\prime}\).