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

Abstract: This paper considers a kind of generalized measure

k a p p a_{s}^{(h)}

of fault tolerance in the

(n, k)

-star graph

S_{n, k}

and determines

k a p p a_{s}^{(h)} (S_{n, k}) = n + h (k - 2) - 1

for

2 l e q s l a n t k l e q s l a n t n - 1

and

0 l e q s l a n t h l e q s l a n t 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].

This page was built for publication: Generalized Measures of Fault Tolerance in (n,k)-star Graphs