Conditional connectivity of star graph networks under embedding restriction

The n-dimensional star graph S-n is one of the most attractive interconnection networks of large scale multiprocessor systems. The k-embedding-restricted (edge) connectivity (eta(k)(S-n)) zeta(k)(S-n) of S-n is defined to be the cardinality of a minimum subset of (edges) nodes, if any, whose deletion disconnects S-n and each node of the remaining components lies in an undamaged k-dimensional substar S-k. In this paper, we investigate the k-embedding-restricted (edge) connectivity of S-n and determine the values of eta(k)(S-n) and zeta(k)(S-n) for some k's. (C) 2012 Elsevier Inc. All rights reserved.