Disjoint paths in hypercubes with prescribed origins and lengths

Given (i) any k vertices u1, u2,⋯, u k (1 ≤ k < n) in the n-cube Qn, where (u 1, u2), (u3, u4),⋯, (u 2m-1, u2m) (m ≤ ⌊ k/2⌋ ) are edges of the same dimension, (ii) any k positive integers a1, a 2,⋯, ak such that a1, a 2,⋯, a2m are odd and a2m + 1,⋯, ak are even, with a1 + a2 +⋯ + a k = 2n, and (iii) k subsets W1, W 2,⋯, Wk of V(Qn) with |Wi| ≤ n - k and if ai = 1, then ui ∉ Wi, for 1 ≤ i ≤ k, we show that there exist k vertex-disjoint paths P (1), P(2),⋯, P(k) in Qn where P(i) contains ai vertices, its origin is ui, and its terminus is in V(Qn) \ Wi, for 1 ≤ i ≤ k. We also prove a similar result which extends two well-known results of Havel, [I. Havel On hamilton circuits and spanning trees of hypercubes, Časopis pro Pěstovani Matematiky, 109 (1984), pp. 135-152.] and Nebeský, [L. Nebeský Embedding m-quasistars into n-cubes, Czech. Math. J. 38 (1988), pp. 705-712]. © 2010 Taylor & Francis.