Title: An extended star graph: a proposal of a new network topology and its fundamental properties

Authors: Satoru Watanabe, Satoshi Okawa

Addresses: Graduate Department of Computer Systems, the University of Aizu, Tsuruga, Ikki-machi, Aizu-Wakamatsu City, Fukushima 965-8580, Japan. ' Graduate Department of Computer Systems, the University of Aizu, Tsuruga, Ikki-machi, Aizu-Wakamatsu City, Fukushima 965-8580, Japan

Abstract: 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.

Keywords: Cayley graphs; star graphs; degree four Cayley graphs; hypercubes; routing algorithms; diameter; network topology; interconnection networks.

DOI: 10.1504/IJCSE.2006.009932

International Journal of Computational Science and Engineering, 2006 Vol.2 No.1/2, pp.32 - 36

Published online: 03 Jun 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article