Perfect dominating sets on cube-connected cycles. (English) Zbl 0802.05073
Summary: 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 both useful for the construction of efficient algorithms for that structure and indicative of practical design constraints. This paper gives a simple algorithmic method for constructing perfect dominating sets on cube-connected cycles where they exist, and proves nonexistence for all other cases. Specifically, standard perfect dominating sets (distance equal to 1) are shown to exist for cube-connected cycles of order \(k\), \(k\) not equal to 5. Moreover, the existence of perfect dominating sets for all distances greater than 1 is disproved (with the trivial exception—the distance equaling or exceeding the diameter of the graph).
MSC:
05C99 | Graph theory |
05C38 | Paths and cycles |
05C35 | Extremal problems in graph theory |
68W15 | Distributed algorithms |
05C85 | Graph algorithms (graph-theoretic aspects) |
05C12 | Distance in graphs |