Computing the Domination Number of Grid Graphs

• DOI: 10.37236/628
• Publication Date: 2020-01-11T03:44:17Z
• Authors: Samu Alanko; Simon Crevals; Anton Isopoussu; Patric Östergård; Ville Pettersson
• Keywords: 0211 other engineering and technologies; 02 engineering and technology

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.