4.1 Article

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

Journal

Publisher

WORLD SCIENTIFIC PUBL CO PTE LTD
DOI: 10.1142/S0129054119500278

Keywords

Strong Menger connectivity; Cayley graph; transposition generating graphs; maximal local-connectivity; fault-tolerance

Funding

  1. Natural Science Foundation of Fujian Province, China [2018J01419]
  2. National Natural Science Foundation of China [11301217, 61572010]
  3. New Century Excellent Talents in Fujian Province University [JA14168]

Ask authors/readers for more resources

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.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.1
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available