Hamiltonian cycles with prescribed edges in hypercubes

Abstract

Given a set P of at most 2n-3 prescribed edges (n g.e. 2), the n-dimensional hypercube Qn contains a Hamiltonian cycle passing through all edges of P iff the subgraph induced by P consists of pairwise vertex-disjoint paths. This answers a question of Caha and Koubek, who showed that for any n g.e. 3 there are 2n-2 edges of Qn not contained in any Hamiltonian cycle, but that still satisfy the above condition.

Keywords

• Hamiltonian
• cycles
• prescribed
• edges
• hypercubes