期刊
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
卷 30, 期 8, 页码 1301-1315出版社
WORLD SCIENTIFIC PUBL CO PTE LTD
DOI: 10.1142/S0129054119500278
关键词
Strong Menger connectivity; Cayley graph; transposition generating graphs; maximal local-connectivity; fault-tolerance
资金
- Natural Science Foundation of Fujian Province, China [2018J01419]
- National Natural Science Foundation of China [11301217, 61572010]
- New Century Excellent Talents in Fujian Province University [JA14168]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据