Increasing the connectivity of the star graphs
Eddie Cheng, Marc J. Lipman · Networks · 2002
Abstract The star graph Sn proposed by Akers et al. has many advantages over the n‐cube. We show that when a large number of vertices are deleted from Sn the resulting graph can have at most two components, one of which is small. We use this result to solve a successive augmentation problem for Sn. This, in turn, provides extra choices for the topology of large interconnection networks. © 2002 Wiley Periodicals, Inc.