Hamiltonian paths with prescribed edges in hypercubes

Abstract

Given a set P of at most 2n-4 prescribed edges (n>=5) and vertices u and v whose mutual distance is odd, the n-dimensional hypercube contains a hamiltonian path between u and v passing through all edges of P iff the subgraph induced by P consists of pairwise vertex-disjoint paths, none of them having u or v as internal vertices or both of them as endvertices. This resolves a problem of Caha and Koubek.

Keywords

• Hamiltonian
• paths
• prescribed
• edges
• hypercubes