## DIMACS TR: 2000-42

## Perfect Dominating Sets of Grids

### Authors: Italo J. Dejter

**
ABSTRACT
**

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