FAULT-TOLERANT MAXIMAL LOCAL-CONNECTIVITY ON CAYLEY GRAPHS GENERATED BY TRANSPOSITION TREES

摘要

The local connectivity of two vertices is defined as the maximum number of internally vertex-disjoint paths between them. In this paper, we define two vertices as maximally local-connected, if the maximum number of internally vertex-disjoint paths between them equals the minimum degree of these two vertices. Moreover, we show that an (n - 1)-regular Cayley graph generated by transposition tree is maximally local-connected, even if there are at most (n - 3) faulty vertices in it, and prove that it is also (n - 1)-fault-tolerant one-to-many maximally local-connected.