2012/04/19 by Meijie Ma, Yaxing Song, Ma, Meijie +4
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Parallel Computing and Optimization Techniques #Software-Defined Networks and 5G #math.CO
paper · pdf · doi:10.48550/arxiv.1204.4251
arxiv created 2012/04/19 · openalex publication_date 2012/04/19 · arxiv updated 2012/04/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.