The g-good-neighbor diagnosability of (n, k)-star graphs

Many large-scale multiprocessor or multi-computer systems take interconnection networks as underlying topologies. Fault diagnosis is especially important to identify fault tolerability of such systems. The g-good-neighbor (conditional) diagnosability such that every fault-free node has at least g fault-free neighbors is a novel measure of diagnosability. In this paper, we show that the g-good-neighbor diagnosability of the (n, k)-star graph S-n,S-k under the PMC model (2 <= k <= n - 1 and 1 <= g <= n - k) and the comparison model (2 <= k <= n - 1 and 2 <= g <= n - k) is n + g(k -1) -1, respectively. In addition, we derive that 1-good-neighbor diagnosability of S-n,S-k under the comparison model is n + k - 2 for 3 <= k <= n - 1 and n >= 4. As a supplement, we also derive that the g-good-neighbor diagnosability of the (n, 1) -star graph S-n,S-1 (1 <= g <= left perpendicular n/2 right perpendicular - 1 and n >= 4) under the PMC model and the comparison model is left perpendicular n/2 left perpendicular - 1, respectively. (C) 2016 Elsevier B.V. All rights reserved.