Reliability of (n, k)-star network based on g-extra conditional fault

In the wake of rapid development of multiprocessor systems, fault tolerance of processors plays an even more vital role in measuring the reliability of a multiprocessor system. The g-extra connectivity of a multiprocessor system modeled by graph G, denoted by kappa((g) )(0)(G), is the minimum number of nodes whose deletion will disconnect the network and every remaining component has more than g vertices. The g-extra conditional diagnosability of multiprocessor system G, denoted by (t) over tilde (g)(G), is the maximum number of faulty vertices that the system can guarantee to identify under the condition that every fault-free component contains at least g +1 vertices. Only a few achievements have been established on kappa((g))(0)(G) for some special graphs with small g. In this paper, we first determine that the g-extra connectivity of (n, k)-star network S-n,S-k is K-0((g)) (S-n,S-k) = n + g (k-2) - 1 for 2 <= k <= n - 1 and 0 <= g <= n - k and then show that the g-extra conditional diagnosability of S-n,S-k under the PMC model (n >= 4,S- 2 <= k <= n - 1 and 1 <= g <= n - k) and the MM* model (n >= 6, 3 <= k <= n - 3 and 1 <= g <= min {n-k+1/4, k - 2}) is (t) over tilde (g) (S-n,S-k) = n + g(k - 1) - 1, respectively. Meanwhile, we also show that S(n,k )is (n + m (k - 2) - 1)/m-diagnosable under the pessimistic diagnostic strategy. As by-products, we derive the g-extra conditional diagnosability of n-dimensional star graph S-n (n >= 4, g = 1) and n-dimensional group network AN(n)(n >= 4, 1 <= g <= 2) under the PMC model. (C) 2018 Elsevier B.V. All rights reserved.