Generalized Measures of Fault Tolerance in (n,k)-star Graphs

This paper considers a kind of generalized measure ${\kappa }_s^{(h)}$ of fault tolerance in the $(n,k)$-star graph $S_{n,k}$ and determines ${\kappa }_s^{(h)}(S_{n,k})=n+h(k-2)-1$ for $2⩽k⩽n-1$ and $0⩽h⩽n-k$, which implies that at least $n+h(k-2)-1$ vertices of $S_{n,k}$ have to remove to get a disconnected graph that contains no vertices of degree less than $h$. This result contains some known results such as Yang et al. [Information Processing Letters, 110 (2010), 1007-1011].