The 2-domination and Roman domination numbers of grid graphs

MaRDI QIDQ5226829zbMATH OpenFDO

Authors Michaël Rao, Alexandre Talon

Publication date 1 August 2019

Full work available at URL https://arxiv.org/abs/1810.12896, https://dmtcs.episciences.org/5482/pdf

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)

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.

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

Cited in

(7)

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

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)