Fault tolerance of augmented cubes
Meijie Ma, Yaxing Song, Jun‐Ming Xu, Teresa W. Haynes · AKCE International Journal of Graphs and Combinatorics · 2013
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 � 4). This paper determines that the 2-extra connectivity of AQn is 6n 17 for n � 9 and the 2-extra edge-connectivity is 6n 9 for n � 4. That is, for n � 9 (respectively, n � 4), at least 6n 17 vertices (respectively, 6n 9 edges) of AQn have to be removed to get a disconnected graph that contains no isolated vertices and isolated edges. 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.