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, Möbius 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)=-12(k+1)2+(2n-32)(k+1)-(n2-2) for n+1⩽k⩽2n-1. The result implies the crossed cube, the Möbius cube, the twisted cube and the hypercube have the same t/k-diagnosability.