The restricted edge-connectivity and restricted connectivity of augmentedk-aryn-cubes
Ruizhi Lin, Heping Zhang · International Journal of Computer Mathematics · 2015
Augmented k-ary n-cube AQn,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 λ′(G) (κ′(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 AQn,k. Precisely, λ′(AQn,k)=8n−6 for n⩾2; κ′(AQ2,k)=8 for k⩾4, κ′(AQn,3)=8n−11 for n⩾3, κ′(AQn,k)=8n−10 for n⩾3 and k⩾4, but AQ2,3 does not have restricted vertex-cut.