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

Abstract: This paper considers a kind of generalized measure

l a m b d a_{s}^{(h)}

of fault tolerance in the

(n, k)

-star graph

S_{n, k}

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

, and determines

l a m b d a_{s}^{(h)} (S_{n, k}) = m i n (n - h - 1) (h + 1), (n - k + 1) (k - 1)

, which implies that at least

m i n (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.

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