Perfect domination in regular grid graphs

Publication date 15 January 2009

Full work available at URL https://arxiv.org/abs/0711.4343

Cayley graphs cycle products integer lattice parallel total perfect codes total perfect code partitions

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Theory of error-correcting codes and error-detecting codes (94B99)

Abstract: We show there is an uncountable number of parallel total perfect codes in the integer lattice graph

L a m b d a

of

R^{2}

. In contrast, there is just one 1-perfect code in

L a m b d a

and one total perfect code in

L a m b d a

restricting to total perfect codes of rectangular grid graphs (yielding an asymmetric, Penrose, tiling of the plane). We characterize all cycle products

C_{m} i m e s C_{n}

with parallel total perfect codes, and the

d

-perfect and total perfect code partitions of

L a m b d a

and

C_{m} i m e s C_{n}

, the former having as quotient graph the undirected Cayley graphs of

with generator set

1, 2 d^{2}

. For

r > 1

, generalization for 1-perfect codes is provided in the integer lattice of

R^{r}

and in the products of

r

cycles, with partition quotient graph

K_{2 r + 1}

taken as the undirected Cayley graph of

with generator set

1, ..., r

.

Recommendations

Cited in

(29)

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

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