### 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.

Original language | English |
---|---|

Title of host publication | 9th International Conference on Algorithms and Architectures for Parallel Processing |

Pages | 120-122 |

Number of pages | 3 |

Volume | 5574 |

State | Published - 2009 |

### Keywords

- connectivity; local connectivity; fault tolerance; vertex-disjoint path; augmented cube
- STRONG MENGER-CONNECTIVITY; FAULTY VERTICES; TOPOLOGICAL PROPERTIES; STAR GRAPHS; HYPERCUBE; COMPONENT; NETWORKS

## Fingerprint Dive into the research topics of 'Maximally Local Connectivity on Augmented Cubes'. Together they form a unique fingerprint.

## Cite this

Chen, Y-C., Chen, M-H., & Tan, J-M. (2009). Maximally Local Connectivity on Augmented Cubes. In

*9th International Conference on Algorithms and Architectures for Parallel Processing*(Vol. 5574, pp. 120-122)