# Domination and Independent Domination in Extended Supergrid Graphs +
## 2 Preliminaries  
In this section, we define the notation used in the paper and present results in the literature that are relevant to our work. For graph theory terms not defined here, the reader is referred to [32]. Let \(G\) be an undirected and simple graph with a vertex set \(V(G)\) and an edge set \(E(G)\). A (simple) path \(P\) in \(G\), expressed as \(v_{1}\to v_{2}\rightarrow\ldots\to v_{|P|-1}\to v_{|P|}\), is a sequence \((v_{1},v_{2},\ldots,v_{|P|-1},v_{|P|})\) of distinct vertices such that \((v_{i},v_{i+1})\in E(G)\) for \(1\leqslant i<|P|\). We use \"\(v_{i}\in P\)\" to mean \"\(v_{i}\) is a vertex that appears in \(P\)\" and the edge \"\((v_{i},v_{i+1})\in P\)\" to mean \"\(P\) visits edge \((v_{i},v_{i+1})\)\". The path from vertex \(v_{1}\) to vertex \(v_{k}\) is represented as the \((v_{1},v_{k})\)-path, and to avoid confusion we use \(P_{n}\) to denote a path with \(n\) vertices. To simplify notation, we use % for modulo arithmetic throughout the rest of this paper. The following lemma shows the domination and independent domination numbers \(\gamma(P_{n})\) and \(\gamma_{\text{ind}}(P_{n})\) of path \(P_{n}\) provided in [30], and can be easily proven by induction on \(n\). **Lemma 1** (see [30]). : \(\gamma(P_{n})=\gamma_{\text{ind}}(P_{n})=\lfloor\frac{n+2}{3}\rfloor=\lceil \frac{n}{3}\rceil\)_, where \(n\) denotes the number of vertices in path \(P_{n}\)._  
Due to the above lemma, the following proposed graph classes do not contain paths as graph subclasses. We introduce extended supergrid graphs and its subclasses of graphs as follows. Let \(S^{\infty}\) be an infinite graph such that its vertex set \(V(S^{\infty})\) contains all points of the Euclidean plane with integer coordinates and its edge set \(E(S^{\infty})=\{(u,v)|\mid u_{x}-v_{x}\rvert\leqslant 1\text{ and }|u_{y}-v_{y}|\leqslant 1\}\), where \(\mu_{x}\) and \(\mu_{y}\) represent the \(x\) and \(y\) coordinates of vertex \(\mu\), respectively, expressed as \(\mu=(\mu_{x},\mu_{y})\) for \(\mu\in V(S^{\infty})\). We call \(S^{\infty}\) the _two-dimensional integer supergrid_. Suppose \((u,v)\in E(S^{\infty})\). In the graph we represent, when \(u_{y}<v_{y}\), this indicates that vertex \(u\) is above \(v\), and when \(u_{x}<v_{x}\), \(u\) is to the left of \(v\). If \(u_{x}=v_{x}\) (respectively, \(u_{y}=v_{y}\)), then \((u,v)\) is called a vertical (respectively, horizontal) edge; otherwise, it is called a diagonal edge. There are two types of diagonal edges \((u,v)\): if \(v_{x}=u_{x}-1\) and \(v_{y}=u_{y}+1\), then diagonal edge \((u,v)\) is called \(l\)-skewed; otherwise, it is called \(r\)-skewed. In our graph representation, when \((u,v)\) is a \(l\)-skewed diagonal edge and \(u\) is above \(v\), \(u\) is located at the upper right of \(v\) in the plane; otherwise, \(u\) is located in the upper left of \(v\) in the plane. The _two-dimensional integer grid_\(G^{\infty}\) is an infinite graph that satisfies \(V(G^{\infty})=V(S^{\infty})\) and \(E(G^{\infty})=\{(u,v)|\mid(u,v)\) is a horizontal or vertical edge\(\}\). In addition, the _two-dimensional triangular integer grid_\(T^{\infty}\) is an infinite graph satisfying \(V(T^{\infty})=V(S^{\infty})\) and \(E(T^{\infty})=\{(u,v)|\mid(u,v)\) is a horizontal, vertical, or \(r\)-skewed diagonal edge\(\}\). For example, Figure 1a-c depicts partial fragments of the infinite graphs \(G^{\infty}\), \(T^{\infty}\) and \(S^{\infty}\), respectively. An _extended supergrid graph_ is a finite _connected_ subgraph of \(S^{\infty}\), while a _grid graph_ (respectively, _triangular grid graph_, _supergrid graph_) is a finite and _vertex-induced_ subgraph of \(G^{\infty}\) (respectively, \(T^{\infty},S^{\infty}\)). Note that an extended supergrid graph is not necessarily a vertex-induced subgraph of \(S^{\infty}\). Thus, extended supergrid graphs contain grid graphs, triangular grid graphs, and supergrid graphs as subclasses of graphs.