A kind of conditional fault tolerance of alternating group graphs

A vertex subset F is a k-restricted 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 k-restricted vertex-cut of G is the k-restricted connectivity of G  , denoted by κk(G)κk(G). This parameter measures a kind of conditional fault tolerance of networks. In this paper, we show that for the n  -dimensional alternating group graph AGnAGn, κ2(AG4)=4κ2(AG4)=4 and κ2(AGn)=6n−18κ2(AGn)=6n−18 for n⩾5n⩾5.

Research highlights► The restricted vertex connectivity κ1κ1 for alternating group graph is determined. ► The restricted vertex connectivity κ2κ2 for alternating group graph is determined.