The \(h\)-restricted connectivity of balanced hypercubes (Q2235266)

The restricted connectivity is a measure of fault-tolerance in multiprocessing systems. The \(h\)-restricted connectivity of a graph \(G\), denoted by \(\kappa^h(G)\), is the minimum cardinality of the vertex subset \(F\) such that \(G-F\) is disconnected and the degree of each component is at least \(h\). This concept, proposed by \textit{A. H. Esfahanian} [``Generalized measures of fault tolerance with application to \(n\)-cube networks'', IEEE Trans. Comput. 38, No. 11, 1586--1591 (1989)], is a kind of conditional connectivity. In this paper, the author studies the \(h\)-restricted connectivity for the \(n\)-dimensional balanced hypercube \(BH_n\), and shows that \(\kappa^{2h}(BH_n) = \kappa^{2h-1}(BH_n) = 4^h(n - h)\), where \(1\leq h\leq \lfloor \frac n 2 \rfloor\) and \(n\geq 2\).