Quasi-efficient domination in grids

Original · EN

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,n ≥ 5 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[₁,₂](Pₘ Pₙ), the minimum cardinality of an independent [1,2]-set for the grid graph Pₘ Pₙ. We calculate i[₁,₂](Pₘ Pₙ) for 2≤ m≤ 13, n≥ m using this algorithm, meanwhile the parameter for grids with 14≤ m≤ n is obtained through a quasi-regular pattern that, in addition, provides an independent [1,2]-set of minimum size.