Fault-tolerance of (n,k)(n,k)-star networks

This paper considers a refined measure κs(h) for the fault-tolerance of a network and, for the generalized star network Sn,kSn,k, determines κs(h)(Sn,k)=n+h(k-2)-1 for 2⩽k⩽n-12⩽k⩽n-1 and 0⩽h⩽n-k0⩽h⩽n-k, which implies that at least n+h(k-2)-1n+h(k-2)-1 vertices of Sn,kSn,k have to be removed to get a disconnected graph without vertices of degree less than h  . This work generalizes some known results. When the (n,k)(n,k)-star graph is used to model the topological structure of a large-scale parallel processing system, this result can provide a more accurate measure for the fault tolerance of the system.