Sequential diagnosis for BC graphs

Sequential diagnosis is a more practical approach to fault diagnosis of multicomputer networks, when the diagnosability of one-step diagnosis is bounded by the minimum vertex degree in its interconnection graph. The BC graphs (bijective connection graphs) are a class of newly introduced interconnection topologies, which include hypercubes, twisted cubes, Möbius cubes and crossed cubes, etc. This paper describes a generalized sequential diagnosis algorithm for BC graphs under PMC model. It is shown that BC graphs of n dimensions are Ω(N log log N/log N)-diagnosable, where N = 2n is the total number of nodes of a BC graph.