# Domination and Independent Domination in Extended Supergrid Graphs +
## 2 Preliminaries
A _diagonal supergrid graph_ is an extended supergrid graph with an edge set that contains at least one \(l\)-skewed and one \(r\)-skewed diagonal edge, and a _triangular supergrid graph_ is an extended supergrid graph such that its edge set contains at least one \(r\)-skewed diagonal edge and no \(l\)-skewed diagonal edges. In general, a diagonal supergrid graph is not necessarily a supergrid graph, and vice versa. The same applies to triangular supergrid graphs and triangular grid graphs. Let \(\mathcal{C}_{e}\), \(\mathcal{C}_{g}\), \(\mathcal{C}_{s}\), \(\mathcal{C}_{d}\), \(\mathcal{C}_{\tau}\), and \(\mathcal{C}_{t}\) be the graph classes of extended supergrid, grid, supergrid, diagonal supergrid, triangular supergrid, and triangular grid graphs, respectively. Then, \(\mathcal{C}_{g},\mathcal{C}_{s},\mathcal{C}_{d},\mathcal{C}_{\tau},\mathcal{C }_{t}\subset\mathcal{C}_{e}\), \(\mathcal{C}_{g}\cap\mathcal{C}_{s}=\mathcal{C}_{g}\cap\mathcal{C}_{t}=\mathcal{ C}_{s}\cap\mathcal{C}_{t}=\emptyset\), \(\mathcal{C}_{s}\cap\mathcal{C}_{d}\
eq\emptyset\), and \(\mathcal{C}_{\tau}\cap\mathcal{C}_{t}\
eq\emptyset\). Figure 2 shows the relationship among these graph classes and indicates the complexities of the studied problems for these graph classes. Obviously, all grid graphs are bipartite [33] and planar; however, (extended, diagonal, triangular) supergrid graphs and triangular grid graphs may not be bipartite. Let \(G_{g}\), \(G_{s}\), and \(G_{t}\) be a grid, supergrid, and triangular grid graph, respectively. Let \(\
u\in V(G_{g})\), \(\mu\in V(G_{s})\), and \(\omega\in V(G_{t})\). Then, \(N_{G_{g}}(\
u)\subseteq\{(v_{x},v_{y}+1),(v_{x},v_{y}-1),(v_{x}+1,v_{y}),(v_{x} -1,v_{y})\}\), \(N_{G_{s}}(\mu)\subseteq\{(\mu_{x},\mu_{y}+1),(\mu_{x},\mu_{y}-1),(\mu_{x}+1, \mu_{y}),(\mu_{x}-1,\mu_{y}),(\mu_{x}-1,\mu_{y}-1),(\mu_{x}-1,\mu_{y}+1),(\mu_{ x}+1,\mu_{y}-1),(\mu_{x}+1,\mu_{y}+1)\}\), and \(N_{G_{\tau}}(\omega)\subseteq\{(\omega_{x},\omega_{y}+1),(\omega_{x},\omega_{ y}-1),(\omega_{x}+1,\omega_{y}),(\omega_{x}-1,\omega_{y}),(\omega_{x}-1,\omega_{y}-1),( \omega_{x}+1,\omega_{y}+1)\}\). That is, \(deg_{G_{g}}(\
u)\leqslant 4,deg_{G_{s}}(\mu)\leqslant 8\), and \(deg_{G_{t}}(\omega)\leqslant 6\). A _rectangular grid_ graph, denoted \(G_{m\times n}\), is the Cartesian product of paths \(P_{m}\) and \(P_{n}\); thus, \((u,v)\in E(G_{m\times n})\) if and only if their distance is 1, that is, \(|u_{x}-v_{x}|+|u_{y}-v_{y}|=1\), where \(P_{i}\) is the simple path with \(i\) vertices. A _rectangular supergrid_ (called _King's_) graph, denoted \(R_{m\times n}\), is the strong product of paths \(P_{m}\) and \(P_{n}\); thus, \((u,v)\in E(R_{m\times n})\) if and only if their distance is less than or equal to \(\sqrt{2}\), that is, \(0\leqslant|u_{x}-v_{x}|\leqslant 1\) and \(0\leqslant|u_{y}-v_{y}|\leqslant 1\). A rectangular triangular-supergrid graph, denoted \(T_{m\times n}\), is obtained from \(G_{m\times n}\) by adding edges \((u,v)\) for \(u,v\in V(G_{m\times n})\), \(u_{x}=v_{x}-1\), and \(u_{y}=v_{y}-1\), i.e., adding diagonal \(r\)-skewed edge to each square of \(G_{m\times n}\). Then, for \(v\in V(G_{m\times n})\), \(u\in V(R_{m\times n})\) and \(w\in V(T_{m\times n})\), we have \(deg_{G_{m\times n}}(v)\leqslant 4,\)\(deg_{R_{m\times n}}(u)\leqslant 8\), and \(deg_{T_{m\times n}}(v)\leqslant 6\). Furthermore,  
Figure 1: Partial fragments of (**a**) \(G^{\infty}\), (**b**) \(T^{\infty}\), and (**c**) \(S^{\infty}\). Figure 2: The containment relations among the classes of extended supergrid, grid, supergrid, diagonal supergrid, triangular supergrid, and triangular grid graphs, where \(\mathcal{C}\rightarrow\mathcal{C}^{\prime}\) indicates that \(\mathcal{C}^{\prime}\) is a subclass of \(\mathcal{C}\). NP-c = NP-complete, P = Polynomial, and? = unknown for the studied problems. for \(m,n\geqslant 2\), \(2\leqslant deg_{\alpha_{m\times n}}(v)\), \(3\leqslant deg_{R_{m\times n}}(u)\), and \(2\leqslant deg_{T_{m\times n}}(w)\).