Menu
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 \( \ominus \) of running time \( O(2^{m+n}) \). Extending \( \ominus \) to infinite grid graphs of width \( m – 1 \), periodicity makes the binary decision tree of \( \ominus \) 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 \( \ominus \), for the growth and determination of which a speedier algorithm exists. 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 \( \ominus \), 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 \( \textbf{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.