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.

    https://doi.org/10.46298/dmtcs.1336
    Source: arXiv.org:1511.06568
    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
    Licence: Attribution 4.0 International (CC BY 4.0)

    Share and export

    Consultation statistics

    This page has been seen 742 times.
    This article's PDF has been downloaded 568 times.