Matchings extend to Hamiltonian cycles in hypercubes

Importance: Medium ✭✭
Recomm. for undergrads: yes
Posted by: Jirka
on: September 28th, 2007

\begin{question} Does every \Def[matching]{matching} of \Def[hypercube]{hypercube} extend to a \Def[Hamiltonian cycle]{Hamiltonian path}? \end{question}

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 \Def[perfect matching]{matching} of hypercube extends to a Hamiltonian cycle.

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{}


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

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

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

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

* indicates original appearance(s) of problem.