A Lower Bound for the Domination Number of Complete Grid Graphs

Abstract

We use a dynamic programming algorithm to establish a lower bound on the domination number of complete grid graphs $G_{m,n}$. The bound is within $5$ of a known upper bound that has been conjectured to be the exact domination number of the complete grid graphs.