77
Views
6
CrossRef citations to date
0
Altmetric
Section A

Disjoint paths in hypercubes with prescribed origins and lengths

, &
Pages 1692-1708 | Received 13 Sep 2007, Accepted 09 Sep 2008, Published online: 22 Jul 2009
 

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 |≤nk and if a i =1, then u i ¬∈W i , for 1≤ik, 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≤ik. 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ĕstování Matematiky, 109 (1984), pp. 135–152.] and Nebeský, [L. Nebeský Embedding m-quasistars into n-cubes, Czech. Math. J. 38 (1988), pp. 705–712].

AMS Subject Classification :

Acknowledgements

The authors thank the referees for their valuable suggestions which improved our presentation.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.