On extra connectivity and extra edge-connectivity of balanced hypercubes

ABSTRACT

The balanced hypercube $B{H}_n$, as a new variation of the hypercube, possesses many attractive properties such that the hypercube dose not have. Given a connected graph G and a non-negative integer g, the g-extra connectivity (resp. g-extra edge-connectivity) of G, denoted by ${\kappa }_g\left(G\right)$ (resp. ${\lambda }_g\left(G\right)$), is the minimal cardinality of a set of vertices (resp. edges) of G, if exists, whose deletion disconnects G and each remaining component contains more than g vertices. In this paper, we show that the 2-extra connectivity of $B{H}_n$ is 4n−4 and 2-extra edge-connectivity of $B{H}_n$ is 6n−4 for $n\ge 2$. Also, we determine 3-extra connectivity of $B{H}_n$ for $n\ge 2$.

KEYWORDS:

• Interconnection networks
• the balanced hypercube
• reliability
• 2-extra edge-connectivity
• 2-extra connectivity

2010 AMS SUBJECT CLASSIFICATIONS:

• 05C40
• 05C90
• 68R10

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

H. Lü http://orcid.org/0000-0003-1033-2386

Additional information

Funding

This research was partially supported by the NSFC (Nos. 11201208 and 11201201).