Linearly many faults in augmented cubes

Abstract

The augmented cube was introduced as a better interconnection network than the hypercube. An interconnection network needs to have good structural properties beyond simple measures such as connectivity. There are many different measures of structural integrity of interconnection networks. In this paper we prove that if vertices are deleted from an augmented cube of dimension n (where g is a quadratic function), the resulting graph will either be connected or will have a large component and small components having at most vertices in total. Additional results on the cyclic vertex-connectivity and the restricted vertex-connectivity of the augmented cubes will also be given.

Keywords:

• interconnection networks
• augmented cubes
• connectivity

Acknowledgement

The authors thank the anonymous referees for their suggestions.

Notes

^1. This paper is part of the author's Ph.D. thesis (see [2]).

^2. [email protected].

^3. [email protected].

^4. Theorems 3.2 and 3.3 have also been proven independently in [1,2].

Additional information

Notes on contributors

Ariana Angjeli

1 1. This paper is part of the author's Ph.D. thesis (see [2]). 2 2. [email protected].

Eddie Cheng

3 3. [email protected].