Originators: F. Ruskey and C. D. Savage
(presented by Jennifer Wise - REGS 2011)
Question: Does every matching of a hypercube extend to a Hamiltonian cycle?
Comments: The answer is positive for the $d$-cube if $d\le 4$. Kreweras' [K] conjectured that every perfect matching of hypercube extends to a Hamiltonian cycle. Fink [F1, F2, F3] proved this. Gregor [G] strengthened the result by showing that given a partition of the hypercube into subcubes of nonzero dimensions, every perfect matching of the hypercube extends on these subcubes to a Hamiltonian cycle if and only if it interconnects them.
References:
[RS] F. Ruskey and C. D. Savage,
SIAM Journal on Discrete Mathematics 6, No.1 (1993) 152-166.
[F1] J. Fink, Perfect matchings extend to Hamilton cycles in hypercubes.
J. Comb. Theory, Ser. B, 97(6):1074-1076, 2007.
[F2] J. Fink, Connectivity of matching graph of hypercube.
SIAM J. Discrete Math. 23 (2009), no. 2, 1100-1109.
[F3] J. Fink. Matching graphs of hypercubes and complete bipartite graphs.
European J. Combin. 30 (2009), no. 7, 1624-1629.
[G] P. Gregor. Perfect matchings extending on subcubes to Hamiltonian cycles of
hypercubes. Discrete Math. 309 (2009), no. 6, 1711–1713.
[K] G. Kreweras, Matchings and Hamiltonian cycles on hypercubes, Bull. Inst.
Combin. Appl. 16 (1996), 87--91.