The super connectivity of augmented cubes

The augmented cube AQn, proposed by Choudum and Sunitha [S.A. Choudum, V. Sunitha, Augmented cubes, Networks 40 (2) (2002) 71–84], is a (2n−1)-regular (2n−1)-connected graph (n≠3). This paper determines that the super connectivity of AQn is 4n−8 for n⩾6 and the super edge-connectivity is 4n−4 for n⩾5. That is, for n⩾6 (respectively, n⩾5), at least 4n−8 vertices (respectively, 4n−4 edges) of AQn are removed to get a disconnected graph that contains no isolated vertices. When the augmented cube is used to model the topological structure of a large-scale parallel processing system, these results can provide more accurate measurements for reliability and fault tolerance of the system.