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 \(BH_n\) is \(m\)-extendable for every \(m\) with \(1 \leq m \leq 2n – 2\), and our result is optimal.