Super connectivity of balanced hypercubes

摘要

The reliability of an interconnection network is an important issue for multiprocessor systems. In this paper, we study a reliability measure, called super connectivity, in the balanced hypercube BHn, which is a variant of the hypercube. We show that the super connectivity of BHn is 4n-4 and the super edge-connectivity of BHn is 4n-2 for n⩾2. That is, to become a disconnected graph containing no isolated vertex, we need to remove at least 4n-4 vertices (resp. 4n-2 edges) from BHn.