Hamiltonicity of hypercubes with a constraint of required and faulty edges

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.