Symmetric Property and Reliability of Balanced Hypercube
Jin‐Xin Zhou, Zhen-Lin Wu, Shi-Chen Yang, Kui-Wu Yuan · IEEE Transactions on Computers · 2014
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)$.