Tomáš Dvořák - Matchings of quadratic size extend to long cycles in hypercubes

dmtcs:1336 - Discrete Mathematics & Theoretical Computer Science, September 1, 2016, Vol. 18 no. 3 - https://doi.org/10.46298/dmtcs.1336
Matchings of quadratic size extend to long cycles in hypercubesArticle

Authors: Tomáš Dvořák ORCID

    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.


    Volume: Vol. 18 no. 3
    Section: Graph Theory
    Published on: September 1, 2016
    Accepted on: September 1, 2016
    Submitted on: August 31, 2016
    Keywords: Computer Science - Discrete Mathematics,05C38, 05C45, 05C70,G.2.2

    Consultation statistics

    This page has been seen 654 times.
    This article's PDF has been downloaded 530 times.