Efficient domination in grid graphs (Q6625100)

A subset \(S\) of vertices of a graph \(G\) is an efficient dominating set if the closed neighborhoods of vertices of \(S\) partition the vertex set of \(G\). This paper considers the minimum number of vertices that can be removed from an \(m\times n\) grid graph so that the remaining graph has an efficient dominating set. Different upper bounds on this number are constructed. The integer programming model is used to verify that the obtained upper bound is optimal for all values \(4\le m\), \(n\le 16\). It remains open whether the bounds are optimal in general.