LINEARLY MANY FAULTS IN (n, k)-STAR GRAPHS
ALLEN YUAN, Eddie Cheng, László Lipták · International Journal of Foundations of Computer Science · 2011
The star graph proposed by [1] has many advantages over the n-cube. However it suffers from having large gaps in the number of possible vertices. The (n,k)-star graph was proposed in [18] to address this issue. Since it is a generalization of the star graph, it retains many of the nice properties of the star graph. There are many different measures of structural integrity of interconnection networks. In this paper, we prove results of the following type for the (n,k)-star graph. If n + (r - 1)k - g(r) vertices are deleted from an (n,k)-star graph, the resulting graph will either be connected or has a large component and small components having at most r - 1 vertices in total. Additional results on conditional vertex connectivity and cycle connectivity will also be given.