10
$\begingroup$

Given that $Q_d$ is the hypercube graph of dimension $d$ then it is a known fact (not so trivial to prove though) that given a perfect matching $M$ of $Q_d$ ($d\geq 2$) it is possible to find another perfect matching $N$ of $Q_d$ such that $M \cup N$ is a Hamiltonian cycle in $Q_d$.

The question now is - given a (non necessarily perfect) matching $M$ of $Q_d$ ($d\geq 2$) is it possible to find a set of edges $N$ such that $M \cup N$ is a Hamiltonian cycle in $Q_d$.

The statement is proven to be true for $d \in\{2,3,4\}$.

$\endgroup$
15
$\begingroup$

This is a known open problem. See "Matchings extend to Hamiltonian cycles in hypercubes" over at the Open Problem Garden.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.