The 2-domination and Roman domination numbers of grid graphs

zbMATH Open1441.05175arXiv1810.12896MaRDI QIDQ5226829FDOQ5226829

Authors: Michaël Rao, Alexandre Talon 

Publication date: 1 August 2019

Abstract: 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!imes!m$ grid, hereby confirming the results found by Lu and Xu, and Shaheen et al. for $nleq4$ 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.

Full work available at URL: https://arxiv.org/abs/1810.12896

Recommendations

• scientific article; zbMATH DE number 7366787
• On the computational complexity of Roman\(\{2\}\)-domination in grid graphs
• Roman domination in subgraphs of grids
• Computing the domination number of grid graphs
• scientific article; zbMATH DE number 4008448

zbMATH Keywords

2-dominationdominationRoman dominationgrid graphstransfer matrixCartesian product of paths$(\min,+)$-algebra

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cited In (7)

• The 2-domination number of cylindrical graphs
• Distance-2 domatic numbers of grid graphs
• On the 2-domination Number of Cylinders with Small Cycles
• Multiple Domination
• Rainbow Domination in Graphs
• Complexity results on \(k\)-independence in some graph products
• Asymptotic growth rate of square grids dominating sets: a symbolic dynamics approach

This page was built for publication: The 2-domination and Roman domination numbers of grid graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5226829)