Symmetric Property and Reliability of Balanced Hypercube.

Huang and Wu in [IEEE Transactions on Computers 46 (1997) 484-490] introduced the balanced hypercube BH_n as an interconnection network topology for computing systems, and they proved that BH_n is vertex-transitive. However, some other symmetric properties, say edge-transitivity and arc-transitivity, of BH_n remained unknown. In this paper, we solve this problem and prove that BH_n is an arc-transitive Cayley graph. Using this, we also investigate some reliability measures, including super-connectivity, cyclic connectivity, etc., in BH_n. First, we prove that every minimum edge-cut of BH_n (n\ge 2) isolates a vertex, and every minimum vertex-cut of BH_n (n\ge 3) isolates a vertex. This is stronger than that obtained by Wu and Huang which shows the connectivity and edge-connectivity of BH_n are 2n. Second, Yang [Applied Mathematics and Computation 219 (2012) 970-975.] proved that for n\ge 2, the super-connectivity of BH_n is 4n-4 and the super edge-connectivity of BH_n is 4n-2. In this paper, we proved that BH_n (n\ge 2) is super-\lambda^\prime but not super-\kappa^\prime . That is, every minimum super edge-cut of BH_n (n\ge 2) isolates an edge, but the minimum super vertex-cut of BH_n (n\ge 2) does not isolate an edge. Third, we also obtain that for n\ge 2, the cyclic connectivity of BH_n is 4n-4 and the cyclic edge-connectivity of BH_n is 4(2n-2). That is, to become a disconnected graph which has at least two components containing cycles, we need to remove at least 4n-4 vertices (resp. 4(4n-2) edges) from BH_n (n\ge 2). [ABSTRACT FROM AUTHOR]