Computing the Domination Number of Grid Graphs

  • Samu Alanko
  • Simon Crevals
  • Anton Isopoussu
  • Patric Östergård
  • Ville Pettersson

Abstract

Let $\gamma_{m,n}$ denote the size of a minimum dominating set in the $m \times n$ grid graph. For the square grid graph, exact values for $\gamma_{n,n}$ have earlier been published for $n \leq 19$. By using a dynamic programming algorithm, the values of $\gamma_{m,n}$ for $m,n \leq 29$ are here obtained. Minimum dominating sets for square grid graphs up to size $29 \times 29$ are depicted.

Published
2011-07-15
Article Number
P141