Matchings of quadratic size extend to long cycles in hypercubes
Authors: Tomáš Dvořák
0000-0002-5853-4254
Tomáš Dvořák
Ruskey and Savage in 1993 asked whether every matching in a hypercube can be
extended to a Hamiltonian cycle. A positive answer is known for perfect
matchings, but the general case has been resolved only for matchings of linear
size. In this paper we show that there is a quadratic function $q(n)$ such that
every matching in the $n$-dimensional hypercube of size at most $q(n)$ may be
extended to a cycle which covers at least $\frac34$ of the vertices.