Conditional diagnosability of multiprocessor systems based on Cayley graphs generated by transpositions

Let Gamma(n) be the symmetric group on {1, 2,..., n} and S be the generating set of Gamma(n). The corresponding Cayley graph is denoted by Gamma(n)(S). If all elements of S are transpositions, a simple way to depict S is to via a graph, called the transposition generating graph of S, denoted by A(S) (or say simply A), where the vertex set of A is {1, 2,..., n}, there is an edge in A between i and j if and only if the transposition (ij) is an element of S, and Gamma(n)(S) is called a Cayley graph obtained from a transposition generating graph A. Conditional diagnosability, proposed by Lai et al, is a novel measure of diagnosability that adds the additional condition that any faulty set cannot contain all of the neighbors of any vertex in a system. There are two well-known diagnostic models, PMC model and MM* model. The conditional diagnosability under the PMC (resp. MM*) model of a graph G, denoted by t(c)(PMC) (G) (resp. t(c)(MM)* (G)), is the maximum value of t is the maximum value of t such that G is conditionally t-diagnosable under the PMC (resp. MM*) model. The conditional diagnosability of many well-known multiprocessor systems has been explored. In this paper, by exploring the structural properties of these Cayley graphs, suppose vertical bar E(A)vertical bar is the number of edges in the transposition generating graph A, we obtain the following results: (1) Under the MM* model, t(c)(MM)* (Gamma(n)(S)) = {3 vertical bar E(A)vertical bar - 6, if A has a triangle; 3 vertical bar E(A)vertical bar - 5, if A has no triangles and A is not a star. (2) Under the PMC model, t(c)(PMC) (Gamma(n)(S)) = {4 vertical bar E(A)vertical bar - 9, if A has a triangle; 4 vertical bar E(A)vertical bar - 7, if A has no triangles and A is not a star. As corollaries, the conditional diagnosability of many kinds of graphs under the MM* model and the PMC model such as Cayley graphs generated by unicyclic graphs, wheel graphs, complete graphs, tree graphs etc. are obtained. (c) 2021 Elsevier B.V. All rights reserved.

Automated summary

The paper examines the conditional diagnosability of Cayley graphs generated by transposition generating graphs and discusses the conditional diagnosability under the MM* and PMC models.