Two node-disjoint paths in balanced hypercubes

摘要

The balanced hypercube BHn proposed by Wu and Huang is a variation of the hypercube. It has been proved that the balanced hypercube is a node-transitive and bipartite graph. Assume that the nodes are divided into two bipartite node sets X and Y,u and x are two different nodes in X, and v and y are two different nodes in Y. In this paper, we prove that there exist two node-disjoint paths P[x,y] and R[u,v] in BHn, and V(P[x,y])∪V(R[u,v])=V(BHn), where n⩾1. The Hamiltonian laceability of BHn which was proved by Xu et al. is also obtained from the corollary of our result.