Wang, Fan; Zhang, Heping Two types of matchings extend to Hamiltonian cycles in hypercubes. (English) Zbl 1363.05156 Ars Comb. 118, 269-283 (2015). Authors’ abstract: F. Ruskey and C. Savage [SIAM J. Discrete Math. 6, No. 1, 152–166 (1993; Zbl 0771.05050)] asked the following question: For \(n\geq 2\), does every matching in \(Q_n\) extend to a Hamiltonian cycle in \(Q_n\)? J. Fink [J. Comb. Theory, Ser. B 97, No. 6, 1074–1076 (2007; Zbl 1126.05080); Eur. J. Comb. 30, No. 7, 1624–1629 (2009; Zbl 1218.05128)] showed that the answer is yes for every perfect matching, thereby proving G. Kreweras’ conjecture [Bull. Inst. Comb. Appl. 16, 87–91 (1996; Zbl 0855.05089)]. In this paper, we prove for \(n\geq 3\) that every matching in \(Q_n\) not covering exactly two vertices at distance 3 extends to a Hamiltonian cycle in \(Q_n\). An edge in \(Q_n\) is an \(i\)-edge if its endpoints differ in the \(i\)th position. We show for \(n\geq 2\) that every matching in \(Q_n\) consisting of edges in at most four types extends to a Hamiltonian cycle in \(Q_n\). Reviewer: Arnfried Kemnitz (Braunschweig) Cited in 1 Document MSC: 05C45 Eulerian and Hamiltonian graphs 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) Keywords:hypercube; Hamiltonian cycle; matching; perfect matching Citations:Zbl 0771.05050; Zbl 1126.05080; Zbl 1218.05128; Zbl 0855.05089 PDFBibTeX XMLCite \textit{F. Wang} and \textit{H. Zhang}, Ars Comb. 118, 269--283 (2015; Zbl 1363.05156)