Reliability analysis of balanced hypercubes

The hypercube is a popular interconnection network for multiprocessor systems. The balanced hypercube, denoted by BH_n, is a variant of the hypercube network. The balanced hypercube reserves some properties of the hypercube and enhances some other properties of it as well. For a multiprocessor system, the reliability of an interconnection network is a major concern. It is well-known that connectivity is a important measure for the reliability of an interconnection network. In this paper, we study a refined reliability measure, called super connectivity, of the balanced hypercube. We show that the super connectivity of BH_n is 4n - 4 for n ≥ 2. That is, at least 4n - 4 vertices need to be removed from BH_n to get a disconnected graph which contains no isolated vertex.