×

Matchings extend to Hamiltonian cycles in 5-cube. (English) Zbl 1377.05104

Summary: F. Ruskey and C. Savage [SIAM J. Discrete Math. 6, No. 1, 152–166 (1993; Zbl 0771.05050)] asked the following question: Does every matching in a hypercube \(Q_n\) for \(n\geq2\) extend to a Hamiltonian cycle of \(Q_n\)? J. Fink [J. Comb. Theory, Ser. B 97, No. 6, 1074–1076 (2007; Zbl 1126.05080); Eur. J. Comb. 30, No. 7, 1624–1629 (2009; Zbl 1218.05128)] confirmed that every perfect matching can be extended to a Hamiltonian cycle of \(Q_n\), thus solved G. Kreweras’ conjecture [Bull. Inst. Comb. Appl. 16, 87–91 (1996; Zbl 0855.05089)]. Also, Fink pointed out that every matching can be extended to a Hamiltonian cycle of \(Q_n\) for \(n\in\{2, 3, 4\}\). In this paper, we prove that every matching in \(Q_5\) can be extended to a Hamiltonian cycle of \(Q_5\).

MSC:

05C45 Eulerian and Hamiltonian graphs
05C38 Paths and cycles
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Software:

MathCheck
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, New York-Amsterdam-Oxford, 1982).; · Zbl 1226.05083
[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; · Zbl 1125.05054
[3] D. Dimitrov, T. Dvořák, P. Gregor and R. Škrekovski, Gray codes avoiding matchings, Discrete Math. Theoret. Comput. Sci. 11 (2009) 123-148.; · Zbl 1192.94070
[4] T. Dvořák, Hamiltonian cycles with prescribed edges in hypercubes, SIAM J. Discrete Math. 19 (2005) 135-144. doi:10.1137/S0895480103432805; · Zbl 1082.05056
[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; · Zbl 1126.05080
[6] J. Fink, Connectivity of matching graph of hypercube, SIAM J. Discrete Math. 23 (2009) 1100-1109. doi:10.1137/070697288; · Zbl 1257.05128
[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; · Zbl 1218.05128
[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; · Zbl 1180.05083
[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.; · Zbl 0855.05089
[11] F. Ruskey and C. Savage, Hamilton cycles that extend transposition matchings in Cayley graphs of \(S_n\), SIAM J. Discrete Math. 6 (1993) 152-166. doi:10.1137/0406012; · Zbl 0771.05050
[12] J. Vandenbussche and D. West, Matching extendability in hypercubes, SIAM J. Discrete Math. 23 (2009) 1539-1547. doi:10.1137/080732687; · Zbl 1207.05161
[13] F. Wang and H.P. Zhang, Two types of matchings extend to Hamiltonian cycles in hypercubes, Ars Combin. 118 (2015) 269-283.; · Zbl 1363.05156
[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; · Zbl 1331.05129
[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; · Zbl 1465.68300
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.