Maximally Local Connectivity on Augmented Cubes

Abstract

Connectivity is all important measurement for the fault tolerance in interconnection networks. It is known that the augmented cube AQ(n) is maximally connected, i.e. (2n - 1)-connected, for n >= 4. By the classical Menger\'s Theorem, every pair of vertices in AQ(n) is connected by 2n - 1 vertex-disjoint paths for n >= 4. A routing with parallel paths can speed up transfers of large amounts of data and increase fault tolerance. Motivated by some research works on networks with faults, we have a further result that for any faulty vertex set F subset of V(AQ(n)) and vertical bar F vertical bar <= 2n - 7 for n >= 4, each pair of non-faulty vertices, denoted by u and v, in AQ(n) - F is connected by min{deg(f)(u), deg(f)(v)} vertex-disjoint fault-free paths, where deg(f)(u) and deg(f)(v) are the degree of u and v in AQ(n) - F, respectively. Moreover, we have another result that for ally faulty vertex set F subset of V(AQ(n)) and vertical bar F vertical bar <= 4n - 9 for n >= 4, there exists a large connected component with at least 2(n) - vertical bar F vertical bar - 1 vertices in AQ(n) - F. In general, a remaining large fault-free connected component also increases fault tolerance.