Incomplete star: an incrementally scalable network based on the star graph
- 1 January 1994
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 5 (1) , 97-102
- https://doi.org/10.1109/71.262593
Abstract
Introduces a new interconnection network for massively parallel systems called the incomplete star graph. The authors describe unique ways of interconnecting and labeling the nodes and routing point-to-point communications within this network. In addition, they provide an analysis of a special class of incomplete star graph called C/sup n/spl minus/1/ graph and obtain the diameter and average distance for this network. For the C/sup n/spl minus/1/ graph, an efficient broadcasting scheme is presented. Furthermore, it is proven that a C/sup n/spl minus/1/ with N nodes (i.e. N=m(n/spl minus/1)!) is Hamiltonian if m=4 or m=3k, and k/spl ne/2.Keywords
This publication has 5 references indexed in Scilit:
- Embedding of cycles and grids in star graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Data communication and computational geometry on the star and pancake interconnection networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1991
- A group-theoretic model for symmetric interconnection networksIEEE Transactions on Computers, 1989
- Incomplete hypercubesIEEE Transactions on Computers, 1988
- Hamiltonian circuits in Cayley graphsDiscrete Mathematics, 1983