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 BHn is vertex-transitive. However, some other symmetric properties, say edge-transitivity and arctransitivity, of BHn 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 > 2) isolates a vertex, and every minimum vertex-cut of BH_n(n ≥ 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 ≥ 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 BHn(n > 2) is super-λ´ but not super-ic´. That is, every minimum super edge-cut of BH_n(n > 2) isolates an edge, but the minimum super vertex-cut of BH_n(n ≥ 2) does not isolate an edge. Third, we also obtain that for n ≥ 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 ≥ 2).