Generalized measures of fault tolerance in hypercube networks

AbstractA vertex subset F is an Rg-cut of a connected graph G if G−F is disconnected and every vertex in G−F has at least g fault-free neighbors in G−F. The cardinality of the minimum Rg-cut of G is the Rg-connectivity of G, denoted by κ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 Rg-cut of hypercubes. Our work strengthens the results of [A.H. Esfahanian, Generalized measure of fault tolerance with application to N-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