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={s1,s2,…,sk}S={s1,s2,…,sk} and T={t1,t2,…,tk}T={t1,t2,…,tk} be two sets of k vertices in different partite sets of the n  -dimensional hypercube QnQn, and let e=|{i|siandtiare adjacent,1⩽i⩽k}|. If n>k+⌈(k-e)/2⌉n>k+⌈(k-e)/2⌉, then there exist k   vertex-disjoint paths P1,P2,…,PkP1,P2,…,Pk, where PiPi connects sisi and titi, for i=1,2,…,ki=1,2,…,k, such that these k   paths contain all vertices of QnQn.