Abstract
Let R and F be two disjoint edge sets in an n-dimensional hypercube Q n . We give two constructing methods to build a Hamiltonian cycle or path that includes all the edges of R but excludes all of F. Besides, considering every vertex of Q n incident to at most n-2 edges of F, we show that a Hamiltonian cycle exists if (A) |R|+2|F| ≤ 2n-3 when |R| ≥ 2, or (B) |R|+2|F| ≤ 4n-9 when |R| ≤ 1. Both bounds are tight. The analogous property for Hamiltonian paths is also given. © 2007 Springer Science+Business Media, LLC.