The restricted edge-connectivity and restricted connectivity of augmented k-ary n-cubes

摘要

Augmented k-ary n-cube AQ(n, k) is proposed as a new interconnection network model by Xiang and Steward [Augmented k-ary n-cubes, Inform. Sci. 181(1) (2011), pp. 239-256]. For a connected graph G, an edge-cut (vertex-cut) S is called a restricted edge-cut (restricted vertex-cut) if G-S contains no isolated vertices. The restricted edge-connectivity (restricted connectivity) of G, denoted by lambda' (G) (kappa' (G)), is the minimum cardinality over all restricted edge-cuts (vertex-cuts) of G. In this paper, we completely determine the restricted (edge-)connectivity of AQ(n, k). Precisely, lambda' (AQ(n, k)) = 8n - 6 for n >= 2; kappa' (AQ(2, k)) = 8 for k >= 4, kappa' (AQ(n, 3)) = 8n - 11 for n >= 3, kappa' (AQ(n, k)) = 8n - 10 for n >= 3 and k >= 4, but AQ(2,3) does not have restricted vertex-cut.