An Explicit Construction of Optimal Dominating Sets in Grid

Abstract

A dominating set in a graph $G$ is a subset of vertices $D$ such that every vertex in $V\setminus D$ is a neighbor of some vertex of $D$. The domination number of $G$ is the minimum size of a dominating set of $G$ and it is denoted by $\gamma (G)$. Also, a subset $D$ of a graph $G$ is a $[1,2]$-set if, each vertex $v\in V\setminus D$ is adjacent to either one or two vertices in $D$ and the minimum cardinality of $[1,2]$-dominating set of $G$, is denoted by ${\gamma }_{[1,2]}(G)$. Chang's conjecture says that for every $16\le m\le n$, $\gamma (G_{m,n})=\lfloor \frac{(n+2)(m+2)}{5}\rfloor -4$ and this conjecture has been proven by Goncalves et al. This paper presents an explicit constructing method to find an optimal dominating set for grid graph $G_{m,n}$ where $m,n\ge 16$ in $O(\text{size of answer})$. In addition, we will show that $\gamma (G_{m,n})={\gamma }_{[1,2]}(G_{m,n})$ where $m,n\ge 16$ holds in response to an open question posed by Chellali et al.

References in corpus (2)

• The Domination Number of Grids
• [1, 2]-sets and [1, 2]-total Sets in Trees with Algorithms