Dept. of Computer Science, Southern Illinois University at Edwardsville

Quentin F. Stout

Computer Science and Engineering, University of Michigan

**Abstract:**
A vertex *v* of a graph *G* *dominates* vertex
*u* if either *v=u* or there is an edge from *v* to *u*.
A set *S* of vertices of *G* is a *dominating set* of
*G* if every vertex of *G* is dominated by a vertex in
*S*. *S* is a *perfect dominating set* (PDS) if each vertex
of *G* is dominated by exactly one vertex in *S*.
A perfect dominating set can also be viewed as a perfect error-correcting
code, where the elements of the dominating set are the codewords.

We study the existence and construction of PDSs in several families of graphs, especially those arising from the interconnection networks of parallel computers. The families include trees, meshes, tori, hypercubes, cube-connected cycles (CCC), cube-connected paths, de Bruijn graphs, arbitrary directed acyclic graphs (DAGs), and series-parallel graphs. For trees, DAGs, and series-parallel graphs we give linear time algorithms that determine if a PDS exists, and which generate a PDS when there is one. For 2- and 3-dimensional meshes, 2-dimensional tori, hypercubes, and cube-connected paths we completely characterize the graphs that have a PDS, and the structure of all PDSs. For higher dimensional meshes and tori, cube-connected cycles, and de Bruijn graphs, we show the existence of a PDS in infinitely many cases, but our characterization is incomplete. Our later paper, Perfect Dominating Sets on Cube-Connected Cycles, completes the characterization for CCCs. Note that meshes, tori, hypercubes, and de Bruijn graphs are all used as topologies of interconnection systems in parallel computers.

One can extend the notion of domination to include distance
*d*-domination for arbitrary positive integer *d*, and our results extend to this case.
This corresponds to *d*-error-correcting codes.

**Keywords:**
perfect domination, perfect error-correcting code, packings, mesh, mesh-connected, torus, hypercube, n-cube, cube-connected cycles, de Bruijn graph, tree, DAG, parallel computer interconnection network

**Complete paper**.
This paper appears in
*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.
- Here is a paper which shows how efficiently compute minimal dominating sets, and many other properties, for certain families of graphs: M Livingston and QF Stout, ``Constant time computation of minimum dominating sets’’, Congressus Numerantium 105 (1994), pp 116-128.
- My papers in graph theory and parallel computing.

Copyright © 2008-2024 Quentin F. Stout |