Generalized measures of fault tolerance in hypercube networks

A vertex subset FF is an RgRg-cut of a connected graph GG if G−FG−F is disconnected and every vertex in G−FG−F has at least gg fault-free neighbors in G−FG−F. The cardinality of the minimum RgRg-cut of GG is the RgRg-connectivity of GG, denoted by κg(G)κg(G). This parameter measures a kind of conditional fault tolerance of networks. In this work, we characterize the smallest components after deleting a minimum RgRg-cut of hypercubes. Our work strengthens the results of [A.H. Esfahanian, Generalized measure of fault tolerance with application to NN-cube networks, IEEE Trans. Comput. 38 (1989) 1586–1591] and [S. Latifi, M. Hegde, M. Naraghi-Pour, Conditional connectivity measures for large multiprocessor systems, IEEE Trans. Comput. 43 (1994) 218–222] and also corrects bugs in them.