PERFECT DOMINATING SETS
Marilynn Livingston, Quentin F. Stout · 1990
A dominating set S of a graph G is perfect if each vertex of G is dominated by exactly one vertex in S. We study the existence and construction of PDSs in families of graphs arising from the interconnection networks of parallel computers. These include trees, dags, series-parallel graphs, meshes, tori, hypercubes, cube-connected cycles, cube-connected paths, and de Bruijn graphs. For trees, dags, and series-parallel graphs we give linear time algorithms that determine if a PDS exists, and generate a PDS when one does. For 2- and 3-dimensional meshes, 2-dimensional tori, hypercubes, and cube-connected paths we completely characterize which graphs 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 not complete. Our results include distance d-domination for arbitrary d. 1 Introduction Suppose G = (V; E) is a graph with vertex se...