Increasing the connectivity of the star graphs

Abstract

Abstract The star graph S n proposed by Akers et al. has many advantages over the n ‐cube. We show that when a large number of vertices are deleted from S n 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 S n . This, in turn, provides extra choices for the topology of large interconnection networks. © 2002 Wiley Periodicals, Inc.