On the t/k-diagnosability of BC networks

To increase the degree of the diagnosability of a system under system-level diagnosis strategies, Somani and Peleg introduced a measure, so called t/k-diagnosis strategy, in which the identified fault-set is allowed to contain at most k fault-free processors. Using this diagnosis strategy, the degree of diagnosability of the BC graphs ( include hypercubes, crossed cubes, Mobius cubes, and twisted cubes, etc. as the subfamily) increases greatly as the number of the fault-free processors in the fault-set increases for 1 <= k <= n. In this paper, we extend the result in [6] on the t/k-diagnosability of BC graphs for 1 <= k <= n by showing that every n-dimensional BC graph is t(n, k)/k-diagnosable when n >= 5 and n + 1 <= k <= 2n - 1, where t(n, k) = -1/2 (k + 1)(2) + (2n - 3/2) (k + 1) (n(2) - 2) for n + 1 <= k <= 2n - 1. The result implies the crossed cube, the Mobius cube, the twisted cube and the hypercube have the same t/k-diagnosability. (C) 2013 Elsevier Inc. All rights reserved.