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

dmtcs:2012 - Discrete Mathematics & Theoretical Computer Science, September 1, 2016, Vol. 18 no. 3
Matchings of quadratic size extend to long cycles in hypercubes

Authors: Dvořák, Tomáš

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.


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


Share

Browsing statistics

This page has been seen 151 times.
This article's PDF has been downloaded 77 times.