Paired many-to-many 2-disjoint path cover of balanced hypercubes with faulty edges

Abstract

As a variant of the well-known hypercube, the balanced hypercube $B{H}_n$ was proposed as a novel interconnection network topology for parallel computing. It is known that $B{H}_n$ is bipartite. Assume that $S=\{s_1,s_2\}$ and $T=\{t_1,t_2\}$ are any two sets of two vertices in different partite sets of $B{H}_n$ ($n\ge 1$). It has been proved that there exist two vertex-disjoint $s_1,t_1$-path and $s_2,t_2$-path of $B{H}_n$ covering all vertices of it. In this paper, we prove that there always exist two vertex-disjoint $s_1,t_1$-path and $s_2,t_2$-path covering all vertices of $B{H}_n$ with at most $2n-3$ faulty edges. The upper bound $2n-3$ of edge faults tolerated is optimal.

arXiv comment30 pages, 9 figures