Tuesday, 3 July 2012

co.combinatorics - Is every matching of the hypercube graph extensible to a Hamiltonian cycle

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$ ($dgeq 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$ ($dgeq 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}$.

No comments:

Post a Comment