Successive Generalizations of Star Graphs

The star graph was proposed as an alternative architecture to hypercube for massively parallel networks. Star graphs have sub logarithmic diameter and degree. However, the number of vertices of star graph form a bottleneck for using them as models for interconnection networks. Two popular remedies were proposed to address this issue, (n,k)-star and arrangement graphs. From another direction, the star graph was recognized as a special case of Cayley graphs whose generators can be associated with a tree. Nevertheless, all these networks appear to be very different and yet share many properties. In this paper, we will solve this mystery by providing a common generalization of all these networks. Moreover, we will show that these networks have good connectivity properties.