Quasi-efficient domination in grids

MaRDI QIDQ6272994zbMATH OpenFDO

Authors Sahar A. Aleid, Jose Cáceres, M. L. Puertas

Publication date 28 April 2016

Abstract: Domination of grids has been proved to be a demanding task and with the addition of independence it becomes more challenging. It is known that no grid with $m,ngeq5$ has an efficient dominating set, also called perfect code, that is, an independent vertex set such that each vertex not in it has exactly one neighbor in that set. So it is interesting to study the existence of independent dominating sets for grids that allow at most two neighbors, such sets are called independent $[1,2]$-sets. In this paper we prove that every grid has an independent $[1,2]$-set, and we develop a dynamic programming algorithm using min-plus algebra that computes $i_{[1,2]}(P_{m}Box{P}_n)$, the minimum cardinality of an independent $[1,2]$-set for the grid graph $P_{m}square{P}_n$. We calculate $i_{[1,2]}(P_{m}Box{P}_n)$ for $2leqmleq13,ngeqm$ using this algorithm, meanwhile the parameter for grids with $14leqmleqn$ is obtained through a quasi-regular pattern that, in addition, provides an independent $[1,2]$-set of minimum size.

This page was built for publication: Quasi-efficient domination in grids

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