Redundance of Complete Grid Graphs

Abstract

The redundance $R(G)$ of a graph $G$ is the minimum, over all dominating sets $S$, of $\sum _{v\in S}(1+\mathrm{deg}(v))$, where $\mathrm{deg}(v)$ is the degree of vertex $v$. We use some dynamic programming algorithms to compute the redundance of complete grid graphs $G_{m,n}$ for $1\le m\le 21$ and all $n$, and to establish good upper and lower bounds on the redundance for larger $m$. We conjecture that the upper bound is the redundance when $m>21$.