The clustered-star graph: a new topology for large interconnection networks

The authors propose a flexible network called the clustered-star (CS) network. An (n-1)-dimensional CS of order m, denoted by CS_n-1^m is an n-dimensional star with (n-m) of its (n-1)-stars missing. The advantage of CS_n-1^m is that from the network size viewpoint, it is scalable by a factor of 1<m<n , as opposed to the (n-1)-star which is scalable only by a factor of n. Furthermore, the complete star graph with some faulty components or with some already allocated substars may result in a clustered-star network which renders the study of this new network important. Basic topological properties of CS_n-1^m are derived and optimal routing and broadcasting algorithms for this network are presented. It is shown that CS_n-1^m is hamiltonian for m=4, and m=3k, k≠2