Perfect domination in rectangular grid graphs
| dc.creator | Dejter, Italo J. | |
| dc.creator | Delgado, Abel A. | |
| dc.date | 2007-11-27 | |
| dc.date.accessioned | 2026-07-07T08:45:27Z | |
| dc.date.available | 2026-07-07T08:45:27Z | |
| dc.description | 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 $Θ$ of running time $O(2^{m+n})$. Extending $Θ$ to infinite grid graphs of width $m-1$, periodicity makes the binary decision tree of $Θ$ 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 $Θ$, 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 $Θ$, which allows to show that these sets $S$ are restrictions of only one total perfect code $S_1$ in the integer lattice graph $Λ$ of $\R^2$. Moreover, the complement $Λ-S_1$ yields an aperiodic tiling, like the Penrose tiling. In contrast, the parallel, horizontal, total perfect codes in $Λ$ are in 1-1 correspondence with the doubly infinite $\{0,1\}$-sequences. | |
| dc.description | 21 pages; 3 figures; accepted for publication in JCMCC | |
| dc.identifier | https://arxiv.org/abs/0711.4345 | |
| dc.identifier | http://arxiv.org/abs/0711.4345 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/142969 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C69 | |
| dc.title | Perfect domination in rectangular grid graphs | |
| dc.type | text |