Matchings extend to Hamiltonian cycles in hypercubes

Importance: Medium ✭✭

Author(s):	Ruskey, Frank
	Savage, Carla

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.

Bibliography

[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.