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 hypercubes

Authors: Tomáš Dvořák ORCID-iD

    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)

    Linked publications - datasets - softwares

    Source : ScholeXplorer IsRelatedTo DOI 10.1016/j.ipl.2008.10.015
    • 10.1016/j.ipl.2008.10.015
    Nearly tight bounds on the number of Hamiltonian circuits of the hypercube and generalizations

    Share and export

    Consultation statistics

    This page has been seen 544 times.
    This article's PDF has been downloaded 462 times.