


























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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。