Mathematics – Combinatorics
Scientific paper
2007-11-27
Mathematics
Combinatorics
21 pages; 3 figures; accepted for publication in JCMCC
Scientific paper
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.
Dejter Italo J.
Delgado Abel A.
No associations
LandOfFree
Perfect domination in rectangular grid graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Perfect domination in rectangular grid graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Perfect domination in rectangular grid graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-248218