Perfect Dominating Sets on Cube-Connected Cycles
Perfect Dominating Sets on Cube-Connected Cycles
复制标题
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
Douglas M. Van Wieren;M. Livingston;Q. Stout
中科院分区：
文献类型：
--
作者：
Douglas M. Van Wieren;M. Livingston;Q. Stout
立方连通圈是一类直径相对较小且结构规则的立方图，这使得它们成为并行体系结构设计的有吸引力的模型。对于任何并行计算的结构模型，完美支配集的存在对于构造该结构的有效算法和指示实际设计约束都是有用的。本文给出了一种构造立方连通圈上完美控制集的简单算法，并证明了在其它情况下完全控制集不存在。具体地说，标准完美控制集（距离等于1）的存在，立方连通循环的阶k，k不等于5。此外，对于所有大于1的距离，完美控制集的存在性被证明是错误的（除了平凡的例外-距离等于或超过图的直径）。
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).