Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871139 | Discrete Applied Mathematics | 2018 | 9 Pages |
Abstract
Let În be the symmetric group on {1,2,â¦,n} and S be the generating set of În. The corresponding Cayley graph is denoted by În(S). If all elements of S are transpositions, a simple way to depict S is 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)âS, and În(S) is called a Cayley graph obtained from a transposition generating graphA. In this paper, by exploring and utilizing the structural properties of these Cayley graphs, we obtain that the pessimistic diagnosability of În(S) is equal to 2|E(A)|â2 if A has no triangles or 2|E(A)|â3 if A has a triangle. As corollaries, the pessimistic diagnosability of many kinds of graphs such as Cayley graphs generated by unicyclic graphs, wheel graphs, complete graphs, and tree graphs is obtained.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Mei-Mei Gu, Rong-Xia Hao,