Disjoint paths in hypercubes with prescribed origins and lengths

Abstract

Given (i) any k vertices u 1 ,u 2 ,?,u k (1?k<n) in the n-cube Q n , where (u 1 ,u 2 ),(u 3 ,u 4 ),?,(u 2m-1 ,u 2m )(m??k/2?) are edges of the same dimension, (ii) any k positive integers a 1 ,a 2 ,?,a k such that a 1 ,a 2 ,?,a 2m are odd and a 2m+1 ,?,a k are even, with a 1 +a 2 +?+a k =2 n , and (iii) k subsets W 1 ,W 2 ,?,W k of V(Q n ) with |W i |?n-k and if a i =1, then u i ?W i , for 1?i?k, we show that there exist k vertex-disjoint paths P (1) ,P (2) ,?,P(k) in Q n where P(i) contains a i vertices, its origin is u i , and its terminus is in V(Q n )/W i , 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,� ?as. P?st. Mat. 109, 135-152 (1984; Zbl 0544.05057)] and Nebesk� [L. Nebesk�, �Embedding m-quasistars into n-cubes,� Czech. Math. J. 38(113), No. 4, 705�712 (1988; Zbl 0677.05021)].