A kind of conditional fault tolerance of (n,k)(n,k)-star graphs

A vertex subset F   is a RkRk-vertex-cut of a connected graph G   if G−FG−F is disconnected and every vertex in G−FG−F has at least k   good neighbors in G−FG−F. The cardinality of the minimum RkRk-vertex-cut of G   is the RkRk-connectivity of G  , denoted by κk(G)κk(G). This parameter measures a kind of conditional fault tolerance of networks. This parameter measures a kind of conditional fault tolerance of networks. In this paper, we determine R1R1-connectivity and R2R2-connectivity of (n,k)(n,k)-star graphs.

Research highlights► The R1R1-connectivity of (n,k)(n,k)-star graphs is determined. ► The R2R2-connectivity of (n,k)(n,k)-star graphs is determined.