Many-to-many n-disjoint path covers in n-dimensional hypercubes

Embedding of paths have attracted much attention in the parallel processing. Many-to-many communication is one of the most central issues in various interconnection networks. In this paper, we investigate the problem of many-to-many unpaired n-disjoint path covers in the n-dimensional hypercube Qn and obtain the following result. For any two sets S and T of n vertices in different parts, Qn has many-to-many unpaired n-disjoint (S,T)-path covers except the case that there exists a vertex v such that NQn(v)=S and v∉T or NQn(v)=T and v∉S.