Geodesic
Extending pairings to Hamiltonian cycles
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 7 (2010), pp. 115-118 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Recently J. Fink proved that every $1$-factor of the complete graph on the vertex set of the hypercube $Q_n$ can be extended to a cycle by adding some edges of this hypercube. We prove that, for $n\ge4$, one can remove some edges of $Q_n$ so that the resulting graph still has this property. Also we give upper and lower bounds on the minimum number of edges of a $2n$-vertex graph having this property.
Keywords: $1$-factor, Hamiltonian cycle, Kreweras Conjecture
Mots-clés : hypercube. 
@article{SEMR_2010_7_a10,
     author = {D. G. Fon-Der-Flaass},
     title = {Extending pairings to {Hamiltonian} cycles},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {115--118},
     year = {2010},
     volume = {7},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2010_7_a10/}
}
TY  - JOUR
AU  - D. G. Fon-Der-Flaass
TI  - Extending pairings to Hamiltonian cycles
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2010
SP  - 115
EP  - 118
VL  - 7
UR  - http://geodesic.mathdoc.fr/item/SEMR_2010_7_a10/
LA  - en
ID  - SEMR_2010_7_a10
ER  - 
%0 Journal Article
%A D. G. Fon-Der-Flaass
%T Extending pairings to Hamiltonian cycles
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2010
%P 115-118
%V 7
%U http://geodesic.mathdoc.fr/item/SEMR_2010_7_a10/
%G en
%F SEMR_2010_7_a10
D. G. Fon-Der-Flaass. Extending pairings to Hamiltonian cycles. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 7 (2010), pp. 115-118. http://geodesic.mathdoc.fr/item/SEMR_2010_7_a10/

[1] J. Fink, “Perfect matchings extend to Hamilton cycles in hypercubes”, J. Combin. Theory Ser. B, 97 (2007), 1074–1076 | DOI | MR | Zbl