Welcome to MathOverflow

Question

6

1

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 >= 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 >= 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}

edited Nov 17 2009 at 14:49

Greg Kuperberg
36.2k●2●116●179

asked Nov 13 2009 at 13:06

Jernej
842●5●18

aorq · Accepted Answer · 2009-11-13 20:27:34Z UTC

11

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

answered Nov 13 2009 at 20:27

aorq
2,450●17●36

Is every matching of the hypercube graph extensible to a Hamiltonian cycle

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.