  A dominating set $S$ in a graph $G$ is said to be perfect if every vertex of
$G$ not in $S$ is adjacent to just one vertex of $S$. Given a vertex subset
$S'$ of a side $P_m$ of an $m\times n$ grid graph $G$, the perfect dominating
sets $S$ in $G$ with $S'=S\cap V(P_m)$ can be determined via an exhaustive
algorithm $\Theta$ of running time $O(2^{m+n})$. Extending $\Theta$ to infinite
grid graphs of width $m-1$, periodicity makes the binary decision tree of
$\Theta$ prunable into a finite threaded tree, a closed walk of which yields
all such sets $S$. The graphs induced by the complements of such sets $S$ can
be codified by arrays of ordered pairs of positive integers via $\Theta$, for
the growth and determination of which a speedier %greedy algorithm exists. %and
their periodic structure, further studied. A recent characterization of grid
graphs having total perfect codes $S$ (with just 1-cubes as induced
components), due to Klostermeyer and Goldwasser, is given in terms of $\Theta$,
which allows to show that these sets $S$ are restrictions of only one total
perfect code $S_1$ in the integer lattice graph ${\Lambda}$ of $\R^2$.
Moreover, the complement ${\Lambda}-S_1$ yields an aperiodic tiling, like the
Penrose tiling. In contrast, the parallel, horizontal, total perfect codes in
${\Lambda}$ are in 1-1 correspondence with the doubly infinite
$\{0,1\}$-sequences.

Combinatorics