Perfect domination in rectangular grid graphs

Abstract: 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 i m e s n

grid graph

G

, the perfect dominating sets

S

in

G

with

S^{'} = S c a p V (P_{m})

can be determined via an exhaustive algorithm

T h e t a

of running time

O (2^{m + n})

. Extending

T h e t a

to infinite grid graphs of width

m - 1

, periodicity makes the binary decision tree of

T h e t a

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

T h e t a

, 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

T h e t a

, which allows to show that these sets

S

are restrictions of only one total perfect code

S_{1}

in the integer lattice graph

L a m b d a

of

R^{2}

. Moreover, the complement

L a m b d a - S_{1}

yields an aperiodic tiling, like the Penrose tiling. In contrast, the parallel, horizontal, total perfect codes in

L a m b d a

are in 1-1 correspondence with the doubly infinite

0, 1

-sequences.

Recommendations

Cited in

(14)

This page was built for publication: Perfect domination in rectangular grid graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3567801)