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

Abstract

Augmented k-ary n-cube $A{Q}_{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 }^{\prime }\left(G\right)$ (${\kappa }^{\prime }\left(G\right)$), is the minimum cardinality over all restricted edge-cuts (vertex-cuts) of G. In this paper, we completely determine the restricted (edge-)connectivity of $A{Q}_{n,k}$. Precisely, ${\lambda }^{\prime }\left(A{Q}_{n,k}\right)=8n-6$ for $n⩾2$; ${\kappa }^{\prime }\left(A{Q}_{2,k}\right)=8$ for $k⩾4$, ${\kappa }^{\prime }\left(A{Q}_{n,3}\right)=8n-11$ for $n⩾3$, ${\kappa }^{\prime }\left(A{Q}_{n,k}\right)=8n-10$ for $n⩾3$ and $k⩾4$, but $A{Q}_{2,3}$ does not have restricted vertex-cut.

Keywords:

• augmented k-ary n-cube
• restricted edge-connectivity
• restricted connectivity

2010 AMS Subject Classifications:

• 05C40
• 05C90

Acknowledgments

The authors thank the anonymous referees for their helpful comments and suggestions.

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

Ruizhi Lin  http://orcid.org/0000-0002-4047-9891

Additional information

Funding

This work is supported by NSFC [grant no. 61073046] and the Fundamental Research Funds for the Central Universities [grant no. lzujbky-2015-211].