The 2-domination and Roman domination numbers of grid graphsArticle
Authors: Michaël Rao ; Alexandre Talon
NULL##NULL
Michaël Rao;Alexandre Talon
We investigate the 2-domination number for grid graphs, that is the size of a
smallest set $D$ of vertices of the grid such that each vertex of the grid
belongs to $D$ or has at least two neighbours in $D$. We give a closed formula
giving the 2-domination number of any $n \!\times\! m$ grid, hereby confirming
the results found by Lu and Xu, and Shaheen et al. for $n \leq 4$ and slightly
correct the value of Shaheen et al. for $n = 5$. The proof relies on some
dynamic programming algorithms, using transfer matrices in (min,+)-algebra. We
also apply the method to solve the Roman domination problem on grid graphs.