DIMACS TR: 2000-42

Perfect Dominating Sets of Grids

Authors: Italo J. Dejter


Let m and n be positive integers. The algorithmic search for perfect dominating sets of the rectangular grid G(m,n) with an initial condition S' defined as an admissible subset of a side G(m,1) of G(m,n) is considered. A binary decision algorithm that generates all perfect dominating sets of G(m,n) satisfying (or containing) such S' is presented, and some related questions and conjectures are posed, leading to consideration of their periodic extendibility to the plane lattice as well as to extremal properties of the grid depth n for a fixed grid width m under the presence of such dominating sets.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-42.ps.gz
DIMACS Home Page