Component connectivity and component diagnosability of the (n,k)-star graph

As a flexible extension derived from the classical star graph, the ( n , k ) -star graph S n , k has been widely adopted to model scalable multiprocessor interconnection networks. This paper studies two reliability parameters that measure the behavior of S n , k when the surviving graph may split into several connected blocks. We first obtain the exact 3,4-component connectivities: κ c 3 ( S n , k ) = 2 n − 3 for n ≥ 6 and 4 ≤ k ≤ n − 2 , and κ c 4 ( S n , k ) = 3 n − 6 for n ≥ 10 and 5 ≤ k ≤ n − 3 . We then prove the 2,3-component diagnosabilities that t c 2 ( S n , k ) = n + k − 3 when n ≥ 5 and 3 ≤ k ≤ n − 2 , and t c 3 ( S n , k ) = 2 n + k − 5 when n ≥ 10 and 5 ≤ k ≤ n − 3 for both the P M C and M M ∗ diagnosis models.