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×m grid, hereby confirming
the results found by Lu and Xu, and Shaheen et al. for n≤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.