Hamiltonian Cycles with Prescribed Edges in Hypercubes
Tomáš Dvořák · SIAM Journal on Discrete Mathematics · 2005
Given a set ${\cal P}$ of at most 2n-3 prescribed edges ($n\ge2$), the n-dimensional hypercube Q n contains a Hamiltonian cycle passing through all edges of ${\cal P}$ iff the subgraph induced by ${\cal P}$ consists of pairwise vertex-disjoint paths. This answers a question of Caha and Koubek, who showed that for any $n\ge3$ there are 2n-2 edges of Q n not contained in any Hamiltonian cycle, but that still satisfy the above condition.