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

Abstract

This paper considers a kind of generalized measure ${\lambda }_s^{(h)}$ of fault tolerance in the $(n,k)$-star graph $S_{n,k}$ for $2⩽k⩽n-1$ and $0⩽h⩽n-k$, and determines ${\lambda }_s^{(h)}(S_{n,k})=\min \{(n-h-1)(h+1),(n-k+1)(k-1)\}$, which implies that at least $\min \{(n-k+1)(k-1),(n-h-1)(h+1)\}$ edges of $S_{n,k}$ have to remove to get a disconnected graph that contains no vertices of degree less than $h$. This result shows that the $(n,k)$-star graph is robust when it is used to model the topological structure of a large-scale parallel processing system.

7 pages, 5 refrences