Matching Extendability of Balanced Hypercubes

Abstract

The balanced hypercube, which is a variant of the hypercube, is proposed as a novel inter-processor network. Among the attractive properties of the balanced hypercube, the most special one is that each processor has a backup processor sharing the same neighborhood. A connected graph $G$ with at least $2m+2$ vertices is said to be $m$-extendable if it possesses a matching of size $m$ and every such matching can be extended to a perfect matching of $G$. In this paper, we prove that the balanced hypercube $B{H}_n$ is $m$-extendable for every $m$ with $1\le m\le 2n–2$, and our result is optimal.