Paired many-to-many disjoint path covers of the hypercubes

In this paper we consider the problem of paired many-to-many disjoint path covers of the hypercubes and obtain the following result. Let S={s"1,s"2,...,s"k} and T={t"1,t"2,...,t"k} be two sets of k vertices in different partite sets of the n-dimensional hypercube Q"n, and let e=|{i|s"iandt"iare adjacent,1=[email protected]?(k-e)/[email protected]?, then there exist k vertex-disjoint paths P"1,P"2,...,P"k, where P"i connects s"i and t"i, for i=1,2,...,k, such that these k paths contain all vertices of Q"n.