Matchings extend to Hamiltonian cycles in hypercubes

Importance: Medium ✭✭
Recomm. for undergrads: yes
Posted by: Jirka
on: September 28th, 2007
Question   Does every matching of hypercube extend to a Hamiltonian cycle?

This question is due to Ruskey and Savage and appears in [RS] (page 19, question 3). The answer is positive for $ d $-cube if $ d \le 4 $.

Fink [F] proved Kreweras' conjecture [K] which asserts that every perfect matching of hypercube extends to a Hamiltonian cycle.


[RS] F. Ruskey and C. D. Savage, SIAM Journal on Discrete Mathematics 6, No.1 (1993) 152-166. download

[F] J. Fink. Perfect matchings extend to Hamilton cycles in hypercubes. J. Comb. Theory, Ser. B, 97(6):1074-1076, 2007. download

[K] G. Kreweras, Matchings and Hamiltonian cycles on hypercubes, Bull. Inst. Combin. Appl. 16 (1996), 87--91.

* indicates original appearance(s) of problem.