Linearly many faults in augmented cubes
Ariana Angjeli, Eddie Cheng, László Lipták · International Journal of Parallel Emergent and Distributed Systems · 2012
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.