Fault-Tolerant Maximal Local-Connectivity on Cayley Graphs Generated by Transpositions

An interconnection network is usually modeled as a graph, in which vertices and edges correspond to processors and communication links, respectively. Connectivity is an important metric for fault tolerance of interconnection networks. A graph G is said to be maximally local-connected if each pair of vertices u and v are connected by min{d(G)(u); d(G)(v)} vertex-disjoint paths. In this paper, we show that Cayley graphs generated by m(>= 7) transpositions are (m - 2)-fault-tolerant maximally local-connected and are also (m -3)-fault-toletant one-to-many maximally local-connected if their corresponding transposition generating graphs have a triangle, (m - 2)-fault-tolerant one-to-many maximally local-connected if their corresponding transposition generating graphs have no triangles. Furthermore, under the restricted condition that each vertex has at least two fault-free adjacent vertices, Cayley graphs generated by m(>= 7) transpositions are (m maximally local-connected if their corresponding transposition generating graphs have no triangles.