Perfect Dominating Sets

Marilynn Livingston
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.


Related Work

Quentin F. Stout Home Copyright © 2008-2016 Quentin F. Stout