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 is said to dominate a 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 is equivalent to a perfect error-correcting code, where the elements of the PDS are the codewords.
Cube-connected cycles are a family of cubic graphs with relatively small diameters and regular structure, making them attractive models for parallel architecture design. The existence of perfect dominating sets for any structural model of parallel computation is useful for solving various algorithmic problems, such as efficient resource allocation. This paper gives a method for constructing PDSs on cube-connected cycles where they exist, and proves nonexistence for all other cases. Specifically, a simple algorithm is given to construct a standard perfect dominating set (distance equal to 1) for cube-connected cycles of all orders except 5, and it is shown that there is no perfect dominating set for order 5. Moreover, the existence of perfect dominating sets for all distances greater than 1 is disproven (with the trivial exception --- the distance equaling or exceeding the diameter of the graph).
Keywords: perfect dominating set, cube-connected cycles, parallel computer, perfect code, vertex-vertex domination, graph theory, regular interconnection network, resource allocation
Complete paper. This appears in Congressus Numerantium 97 (1993), pp. 51-70.
Related Work:
|
Copyright © 2008-2018 Quentin F. Stout |