Geodesic
Matchings of quadratic size extend to long cycles in hypercubes
Discrete mathematics & theoretical computer science, Tome 18 (2015-2016) no. 3.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2016_18_3_a11,
     author = {Dvo\v{r}\'ak, Tom\'a\v{s}},
     title = {Matchings of quadratic size extend to long cycles in hypercubes},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {18},
     number = {3},
     year = {2015-2016},
     doi = {10.46298/dmtcs.1336},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.1336/}
}
TY  - JOUR
AU  - Dvořák, Tomáš
TI  - Matchings of quadratic size extend to long cycles in hypercubes
JO  - Discrete mathematics & theoretical computer science
PY  - 2015-2016
VL  - 18
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.1336/
DO  - 10.46298/dmtcs.1336
LA  - en
ID  - DMTCS_2016_18_3_a11
ER  - 
%0 Journal Article
%A Dvořák, Tomáš
%T Matchings of quadratic size extend to long cycles in hypercubes
%J Discrete mathematics & theoretical computer science
%D 2015-2016
%V 18
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.1336/
%R 10.46298/dmtcs.1336
%G en
%F DMTCS_2016_18_3_a11
Dvořák, Tomáš. Matchings of quadratic size extend to long cycles in hypercubes. Discrete mathematics & theoretical computer science, Tome 18 (2015-2016) no. 3. doi : 10.46298/dmtcs.1336. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.1336/

Cité par Sources :