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