A kind of matchings extend to Hamiltonian cycles in hypercubes

School of Mathematics and Computer Sciences, Nanchang University, Nanchang, Jiangxi 330000, P.R. China

^* Corresponding author: wangfan@ncu.edu.cn

Received: 11 September 2023
Accepted: 27 October 2024

Abstract

Ruskey and Savage asked the following question: Does every matching in Q_n for n ≥ 2 extend to a Hamiltonian cycle of Q_n? Kreweras conjectured that every perfect matching of Q_n for n ≥ 2 can be extended to a Hamiltonian cycle of Q_n. Fink confirmed the conjecture. An edge in Q_n is an edge of direction i if its endpoints differ in the ith position. So all the edges of Q_n can be divided into n directions, i.e., edges of direction 1, …, edges of direction n. The set of all edges of direction i of Q_n is denoted by E_i. In this paper, we obtain the following result. For n ≥ 6, let M be a matching in Q_n with |M| < 10 × 2ⁿ⁻⁵. If M contains edges in at most 5 directions, then M can be extended to a Hamiltonian cycle of Q_n.