Connected Dominating Set of Hypercubes and Star Graphs
Y-Chuang Chen, Ya-Ling Syu · 2012
In wired or wireless networks, routing efficiently among immobile or mobile devices is an important issue. A connected dominating set (CDS) brings benefits to network routing. The CDS can be served as a virtual backbone of a network, and it always adapted easily to new network topology. A virtual backbone is a set of vertices which can help with routing. Any vertex outside the virtual backbone can send messages or signals to another vertex through the virtual backbone. So the virtual backbone has great benefits to routing and management of networks. We may impose a virtual backbone to support short path routing, fault-tolerant routing, multi-casting, and radio broadcasting, etc. In this paper, we focus on constructing the minimum CDS (MCDS) of the n-dimensional hypercubes and n-dimensional star graphs.