Dept. of Computer Science, Southern Illinois University at Edwardsville

Quentin F. Stout

Computer Science and Engineering, University of Michigan

**Abstract:**
Let *G* be a finite graph and let *P(n)* denote an element from a
one-parameter family of graphs, such as a path of length *n*,
a cycle of length *n*,
or a complete binary tree of height *n*. We are concerned with
determining minimum dominating sets of graphs of the form *G x P(n)*.
Using dynamic programming and periodic properties of weighted paths in
finite state spaces, we give a constant time algorithm to produce a
minimum dominating set of
*G x P(n)*, for fixed *G* and all *n*, for the
one-parameter families mentioned above.
Previous researchers had used dynamic programming but had
obtained only linear-time algorithms. We also show how a closed
form expression can be obtained for the minimum domination number
of *G x P(n)*.

This algorithmic approach applies to the determination of all minimum
dominating sets for *G x P(n)*, and to related problems of packings, mispackings, colorings, coverings, maximal matching, partitions, independent
sets, tilings, codes, colorings, etc.
In addition, there are straightforward algorithmic extensions to
many different types of domination, including perfect domination (which
is the same as perfect error-correcting codes)
and to other ways of composing graphs, such as tori, fasciagraphs and rotagraphs.

Here are some open problems and conjectures related to this paper.

Note that an extended version of this paper is in preparation (and may appear in more than one part because it seems to be getting too long, or may never appear, for the same reason). The omitted proofs will be included, other examples will be given, some computational aspects will be touched on, and more extensions will be given.

**Keywords:** covering, domination, packing, mispacking, matching,
perfect domination, perfect error-correcting codes, colorings,
grid graph, product graph, mesh, torus, dynamic programming,
finite state spaces, weighted paths

Complete paper.
This paper appears in *Congressus Numerantium* 105 (1994),
pp. 116-128.

- Perfect Dominating Sets:

- Results for meshes, hypercubes, trees, tori, etc.: M Livingston and QF Stout,``Perfect dominating sets'', Congressus Numerantium 79 (1990), pp. 187-203

- Results for cube-connected cycles: D Van Wieren, M Livingston, and QF Stout,``Perfect dominating sets on cube-connected cycles'', Congressus Numerantium 97 (1993), pp 51-70.

- Results for meshes, hypercubes, trees, tori, etc.: M Livingston and QF Stout,``Perfect dominating sets'', Congressus Numerantium 79 (1990), pp. 187-203
- Graph Theory: an overview of my work and my papers
- Algorithms: an overview of my work and my papers

Copyright © 2005-2016 Quentin F. Stout |