Unpaired many-to-many disjoint path cover of balanced hypercubes

Abstract

The balanced hypercube $B{H}_n$, a variant of the hypercube, was proposed as a desired interconnection network topology. It is known that $B{H}_n$ is bipartite. Assume that $S=\{s_1,s_2,\cdots ,s_{2n-2}\}$ and $T=\{t_1,t_2,\cdots ,t_{2n-2}\}$ are any two sets of vertices in different partite sets of $B{H}_n$ ($n\ge 2$). It has been proved that there exists paired 2-disjoint path cover of $B{H}_n$. In this paper, we prove that there exists unpaired $(2n-2)$-disjoint path cover of $B{H}_n$ ($n\ge 2$) from $S$ to $T$, which improved some known results. The upper bound $2n-2$ of the number of disjoint paths in unpaired $(2n-2)$-disjoint path cover is best possible.

arXiv admin note: text overlap with arXiv:1804.01949