Geodesic
Matchings Extend to Hamiltonian Cycles in 5-Cube
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 1, pp. 217-231.

Voir la notice de l'article provenant de la source Library of Science

Ruskey and Savage asked the following question: Does every matching in a hypercube Qn for n ≥ 2 extend to a Hamiltonian cycle of Qn? Fink confirmed that every perfect matching can be extended to a Hamiltonian cycle of Qn, thus solved Kreweras’ conjecture. Also, Fink pointed out that every matching can be extended to a Hamiltonian cycle of Qn for n ∈ 2, 3, 4. In this paper, we prove that every matching in Q5 can be extended to a Hamiltonian cycle of Q5.
Keywords: hypercube, Hamiltonian cycle, matching 
@article{DMGT_2018_38_1_a17,
     author = {Wang, Fan and Zhao, Weisheng},
     title = {Matchings {Extend} to {Hamiltonian} {Cycles} in {5-Cube}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {217--231},
     publisher = {mathdoc},
     volume = {38},
     number = {1},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a17/}
}
TY  - JOUR
AU  - Wang, Fan
AU  - Zhao, Weisheng
TI  - Matchings Extend to Hamiltonian Cycles in 5-Cube
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 217
EP  - 231
VL  - 38
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a17/
LA  - en
ID  - DMGT_2018_38_1_a17
ER  - 
%0 Journal Article
%A Wang, Fan
%A Zhao, Weisheng
%T Matchings Extend to Hamiltonian Cycles in 5-Cube
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 217-231
%V 38
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a17/
%G en
%F DMGT_2018_38_1_a17
Wang, Fan; Zhao, Weisheng. Matchings Extend to Hamiltonian Cycles in 5-Cube. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 1, pp. 217-231. http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a17/

[1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, New York-Amsterdam-Oxford, 1982).

[2] R. Caha and V. Koubek, Spanning multi-paths in hypercubes, Discrete Math. 307 (2007) 2053–2066. doi:10.1016/j.disc.2005.12.050

[3] D. Dimitrov, T. Dvořák, P. Gregor and R. Škrekovski, Gray codes avoiding matchings, Discrete Math. Theoret. Comput. Sci. 11 (2009) 123–148.

[4] T. Dvořák, Hamiltonian cycles with prescribed edges in hypercubes, SIAM J. Discrete Math. 19 (2005) 135–144. doi:10.1137/S0895480103432805

[5] J. Fink, Perfect matchings extend to Hamilton cycles in hypercubes, J. Combin. Theory Ser. B 97 (2007) 1074–1076. doi:10.1016/j.jctb.2007.02.007

[6] J. Fink, Connectivity of matching graph of hypercube, SIAM J. Discrete Math. 23 (2009) 1100–1109. doi:10.1137/070697288

[7] J. Fink, Matching graphs of hypercubes and complete bipartite graphs, European J. Combin. 30 (2009) 1624–1629. doi:10.1016/j.ejc.2009.03.007

[8] P. Gregor, Perfect matchings extending on subcubes to Hamiltonian cycles of hypercubes, Discrete Math. 309 (2009) 1711–1713. doi:10.1016/j.disc.2008.02.013

[9] L. Gros, Théorie du Baguenodier (Aimé Vingtrinier, Lyon, 1872).

[10] G. Kreweras, Matchings and Hamiltonian cycles on hypercubes, Bull. Inst. Combin. Appl. 16 (1996) 87–91.

[11] F. Ruskey and C. Savage, Hamilton cycles that extend transposition matchings in Cayley graphs of Sn, SIAM J. Discrete Math. 6 (1993) 152–166. doi:10.1137/0406012

[12] J. Vandenbussche and D. West, Matching extendability in hypercubes, SIAM J. Discrete Math. 23 (2009) 1539–1547. doi:10.1137/080732687

[13] F. Wang and H.P. Zhang, Two types of matchings extend to Hamiltonian cycles in hypercubes, Ars Combin. 118 (2015) 269–283.

[14] F. Wang and H.P. Zhang, Small matchings extend to Hamiltonian cycles in hypercubes, Graphs Combin. 32 (2016) 363–376. doi:10.1007/s00373-015-1533-6

[15] E. Zulkoski, V. Ganesh and K. Czarnecki, MathCheck: A Math Assistant via a Combination of Computer Algebra Systems and SAT Solvers, in: A.P. Felty and A. Middeldorp, Proc. CADE-25 (Ed(s)), (LNCS 9195, 2015) 607–622. doi:10.1007/978-3-319-21401-6_41