
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.Comment: 11 pages, 5 figures, presented at ICGT 2018 The program that led to the results is included in the Source directory (see Other formats) Accepted in DMTCS vol 21. Journal version with their template
FOS: Computer and information sciences, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], computer science - discrete mathematics, Discrete Mathematics (cs.DM), mathematics - combinatorics, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], computer science - discrete mathematics, Discrete Mathematics (cs.DM), mathematics - combinatorics, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics, Computer Science - Discrete Mathematics
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 4 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
