most recent 30 from http://mathoverflow.net 2013-05-25T23:55:07Z http://mathoverflow.net/feeds/question/5340 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/5340/is-every-matching-of-the-hypercube-graph-extensible-to-a-hamiltonian-cycle Jernej 2009-11-13T13:06:32Z 2010-09-07T03:13:14Z

<p>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.</p> <p>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.</p> <p>The statement is proven to be true for d in {2,3,4} </p>

http://mathoverflow.net/questions/5340/is-every-matching-of-the-hypercube-graph-extensible-to-a-hamiltonian-cycle/5433#5433 aorq 2009-11-13T20:27:34Z 2009-11-13T20:27:34Z

<p>This is a known open problem. See "<a href="http://garden.irmacs.sfu.ca/?q=op/matchings%5Fextends%5Fto%5Fhamilton%5Fcycles%5Fin%5Fhypercubes" rel="nofollow">Matchings extend to Hamiltonian cycles in hypercubes</a>" over at the Open Problem Garden.</p>