×

Perfect matchings extend to two or more Hamiltonian cycles in hypercubes. (English) Zbl 1400.05189

Summary: G. Kreweras [Bull. Inst. Comb. Appl. 16, 87–91 (1996; Zbl 0855.05089)] conjectured that every perfect matching of a hypercube \(Q_n\) for \(n \geq 2\) can be extended 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 the conjecture to be true. It is more general to ask whether every perfect matching of \(Q_n\) for \(n \geq 2\) can be extended to two or more Hamiltonian cycles of \(Q_n\). In this paper, we prove that every perfect matching of \(Q_n\) for \(n \geq 4\) can be extended to at least \(2^{2^{n - 4}}\) different Hamiltonian cycles of \(Q_n\).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C45 Eulerian and Hamiltonian graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bondy, J.; Murty, U., Graph Theory with Applications, (1976), Macmillan Press: Macmillan Press London · Zbl 1226.05083
[2] Caha, R.; Koubek, V., Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets, J. Graph Theory, 51, 2, 137-169, (2006) · Zbl 1084.05041
[3] Dimitrov, D.; Dvořák, T.; Gregor, P.; Škrekovski, R., Gray codes avoiding matchings, Discrete Math. Theor. Comput. Sci., 11, 123-148, (2009) · Zbl 1192.94070
[4] Dvořák, T., Hamiltonian cycles with prescribed edges in hypercubes, SIAM J. Discrete Math., 19, 135-144, (2005) · Zbl 1082.05056
[5] Dvořák, T.; Fink, J., Gray codes extending quadratic matchings, J. Graph Theory, (2018)
[6] Fink, J., Perfect matchings extend to hamilton cycles in hypercubes, J. Combin. Theory Ser. B, 97, 1074-1076, (2007) · Zbl 1126.05080
[7] Fink, J., Connectivity of matching graph of hypercube, SIAM J. Discrete Math., 23, 2, 1100-1109, (2009) · Zbl 1257.05128
[8] Fink, J., Matching graphs of hypercubes and complete bipartite graphs, European J. Combin., 30, 7, 1624-1629, (2009) · Zbl 1218.05128
[9] Fink, J., Matchings extend into 2-factors in hypercubes, Combinatorica, (2018)
[10] Gregor, P., Perfect matchings extending on subcubes to hamiltonian cycles of hypercubes, Discrete Math., 309, 1711-1713, (2009) · Zbl 1180.05083
[11] Gros, L., Théorie du Baguenodier, (1872), Aimé Vingtrinier: Aimé Vingtrinier Lyon
[12] Kreweras, G., Matchings and hamiltonian cycles on hypercubes, Bull. Inst. Combin. Appl., 16, 87-91, (1996) · Zbl 0855.05089
[13] Liu, J. J.; Wang, Y. L., Hamiltonian cycles in hypercubes with faulty edges, Inform. Sci., 256, 225-233, (2014) · Zbl 1320.68130
[14] Ruskey, F.; Savage, C., Hamilton cycles that extend transposition matchings in Cayley graphs of \(S_n\), SIAM J. Discrete Math., 6, 1, 152-166, (1993) · Zbl 0771.05050
[15] Vandenbussche, J.; West, D. B., Extensions to 2-factors in bipartite graphs, Electron. J. Combin., 20, 1-10, (2013) · Zbl 1295.05188
[16] Wang, W.; Chen, X., A fault-free Hamiltonian cycle passing through prescribed edges in a hypercube with faulty edges, Inform. Process. Lett., 107, 6, 205-210, (2008) · Zbl 1186.68035
[17] Wang, F.; Zhang, H. P., Small matchings extend to Hamiltonian cycles in hypercubes, Graphs Combin., 32, 363-376, (2016) · Zbl 1331.05129
[18] Xu, J. M.; Du, Z. Z.; Xu, M., Edge-fault-tolerant edge-bipancyclicity of hypercubes, Inform. Process. Lett., 96, 146-150, (2005) · Zbl 1184.68117
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.