An extended star graph: a proposal of a new network topology and its fundamental properties
Satoru Watanabe, Satoshi Okawa · International Journal of Computational Science and Engineering · 2006
In the past years, various network architectures for parallel computers have been proposed, for example, hyper cubes or star graphs. These classes of networks are known as Cayley graphs. In recent years, there have been some proposals of new families of interconnection networks, namely, constant degree networks. In this paper, a new interconnection network named extended star graphs is proposed, and it is proved that the extended star graphs have hypercube structure. We also provide a routing algorithm for node-to-node communication on extended star graphs. Based on the algorithm, we obtain an upper bound 2n−1 on the diameter for the n-th order extended star graph.