Fault-tolerance of (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 S n , k , determines ? 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 be removed to get a disconnected graph without vertices of degree less than h. This work generalizes some known results. When the ( 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.