# Domination and Independent Domination in Extended Supergrid Graphs +
## 1 Introduction  
For a graph \(G\), we denote the vertex and edge sets of \(G\) as \(V(G)\) and \(E(G)\), respectively. Let \(v\) be a vertex of \(V(G)\), and let \(S\) be a subset of \(V(G)\). We denote the subgraph induced by \(S\) as \(G[S]\). The degree of vertex \(v\) in \(G\) is denoted by \(deg_{G}(v)\), which represents the number of edges incident with \(v\) in \(G\). The set of neighbors of a vertex \(v\) in \(G\) is denoted by \(N_{G}(v)=\{u\in V(G)|(u,v)\in E(G)\}\) and \(N_{G}[v]=N_{G}(v)\cup\{v\}\). The neighborhood set of vertex set \(S\) in \(G\) is defined as \(N_{G}(S)=\cup_{v\in S}N_{G}(v)-S\) and \(N_{G}[S]=N_{G}(S)\cup S\). Let \(D\subseteq V(G)\); a set \(D\) is said to dominate vertex \(v\) if \(N_{G}[v]\cap D\
eq\emptyset\). In addition, we can say that vertex \(v\) dominates its neighbors and itself. We say that \(D\) dominates \(S\) when \(D\) dominates every vertex of set \(S\). If \(D\) dominates \(V(G)\), set \(D\) is said to be a dominating setof \(G\). The domination number of a graph \(G\), expressed as \(\gamma(G)\), is the minimum size of a dominating set of \(G\). A minimum dominating set of graph \(G\) is a dominating set with size \(\gamma(G)\). The _domination problem_ is to find a minimum dominating set of a graph, and is a well-known NP-complete problem for general graphs [1]. However, the problem remains NP-complete when the input is restricted to certain special classes of graphs, including grid graphs [2], 4-regular planar graphs [1], etc. In the literature, the problems of domination and its variants have been extensively studied. A variant of the domination problem is to find a minimum dominating set that satisfies some special conditions. For example, the connected domination problem is to compute a minimum dominating set such that the subgraph induced by it is connected, and the dominating cycle problem is to find a cycle with the least number of vertices to dominate the input graph. In the past, many scholars have proposed many applications for dominating sets and their variants. For instance, in distributed network applications the domination problem is to find the minimum number of control centers placed in the network to ensure that each node is close to at least one center. In a guard location system, the connected domination problem is to locate the fewest number of guards, allowing them to connect to each other in order to protect each other and monitor other locations. For related concepts and applications of these problems, we refer the reader to two survey books in [3; 4]. In this paper, the domination problem, as well as one variant called the independent domination problem, are studied. A set of vertices is called independent if any two vertices in it are not adjacent. An independent dominating set of a graph \(G\) is a dominating set \(I\) satisfying \(I\) as an independent set. The independent domination number of a graph \(G\), expressed as \(\gamma_{\text{ind}}(G)\), is the minimum cardinality of an independent domination set in \(G\). Because an independent dominating set of a graph \(G\) is a dominating set of \(G\), \(\gamma(G)\leqslant\gamma_{\text{ind}}(G)\) for any graph \(G\). That is, \(\gamma(G)\) provides a trivial lower bound for \(\gamma_{\text{ind}}(G)\). The _independent domination problem_ on graph \(G\) is to find an independent dominating set with size \(\gamma_{\text{ind}}(G)\). This problem is NP-complete for general graphs [1], and remains NP-complete for grid graphs [2], comparability graphs, bipartite graphs [5], sat-graphs [6], line graphs [7], chordal bipartite graphs [8], etc. However, when the input is in some special class of graphs, it allows polynomial-time algorithms, including permutation graphs, interval graphs [9], chordal graphs [10], circular-arc graphs [11], AT-free graphs [12], bounded clique-width graphs [13], etc. For more relevant works on independent domination, we refer the reader to a survey in [14], and more results in [15; 16; 17; 18].