The restricted $h$-connectivity of balanced hypercubes

Abstract

The restricted $h$-connectivity of a graph $G$, denoted by ${\kappa }^h(G)$, is defined as the minimum cardinality of a set of vertices $F$ in $G$, if exists, whose removal disconnects $G$ and the minimum degree of each component of $G-F$ is at least $h$. In this paper, we study the restricted $h$-connectivity of the balanced hypercube $B{H}_n$ and determine that ${\kappa }^1(B{H}_n)={\kappa }^2(B{H}_n)=4n-4$ for $n\ge 2$. We also obtain a sharp upper bound of ${\kappa }^3(B{H}_n)$ and ${\kappa }^4(B{H}_n)$ of $n$-dimension balanced hypercube for $n\ge 3$ ($n\ne 4$). In particular, we show that ${\kappa }^3(B{H}_3)={\kappa }^4(B{H}_3)=12$.

Cited by in corpus (1)

• Structure and substructure connectivity of balanced hypercubes