Premium
Increasing the connectivity of the star graphs
Author(s) -
Cheng Eddie,
Lipman Marc J.
Publication year - 2002
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10045
Subject(s) - star (game theory) , computer science , graph , combinatorics , interconnection , topology (electrical circuits) , mathematics , theoretical computer science , computer network , mathematical analysis
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.