{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T14:53:02Z","timestamp":1778597582853,"version":"3.51.4"},"reference-count":21,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T00:00:00Z","timestamp":1750723200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>The hypercube Qn is a well-known and efficient interconnection network. Ruskey and Savage posed the following question: does every matching in a hypercube Qn for n\u22652 extend to a Hamiltonian cycle? Fink addressed this by proving that every perfect matching extends to a Hamiltonian cycle in Qn, thereby resolving Kreweras\u2019 conjecture. Ruskey and Savage\u2019s problem is still open and has been proven only for small matchings. An edge of Qn is an i-edge when the binary representations of its endpoints differ at the ith coordinate. In this paper, we consider Qn for n\u22653 and show that any matching consisting of edges of at most six types, which does not cover every pair of vertices at a distance of 3, extends to a Hamiltonian cycle.<\/jats:p>","DOI":"10.3390\/sym17070995","type":"journal-article","created":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T10:44:41Z","timestamp":1750761881000},"page":"995","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Kinds of Matchings Extending to Hamiltonian Cycles in Hypercube Networks"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2654-9184","authenticated-orcid":false,"given":"Abid","family":"Ali","sequence":"first","affiliation":[{"name":"College of Mathematics, Taiyuan University of Technology, Wanbailin District, Taiyuan 030024, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weihua","family":"Yang","sequence":"additional","affiliation":[{"name":"College of Mathematics, Taiyuan University of Technology, Wanbailin District, Taiyuan 030024, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-4444-0370","authenticated-orcid":false,"given":"Gohar","family":"Ali","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Islamia College Peshawar, Peshawar 25120, Khyber Pakhtunkhwa, Pakistan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8042-1806","authenticated-orcid":false,"given":"Ioan-Lucian","family":"Popa","sequence":"additional","affiliation":[{"name":"Department of Computing, Mathematics, and Electronics, 1 Decembrie 1918 University of Alba Iulia, 510009 Alba Iulia, Romania"},{"name":"Faculty of Mathematics and Computer Science, Transilvania University of Brasov, Iuliu Maniu Street 50, 500091 Brasov, Romania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-0160-4031","authenticated-orcid":false,"given":"Dilara Akter","family":"Mitu","sequence":"additional","affiliation":[{"name":"College of Mathematics, Taiyuan University of Technology, Wanbailin District, Taiyuan 030024, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,6,24]]},"reference":[{"key":"ref_1","unstructured":"Gros, L. (1872). Theorie du Baguenodier, Aim\u00e9 Vingtrinier."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Alahmadi, A., Aldred, R.E., Alkenani, A., Hijazi, R., Sol\u00e9, P., and Thomassen, C. (2015). Extending a perfect matching to a Hamiltonian cycle. Discret. Math. Theor. Comput. Sci., 17.","DOI":"10.46298\/dmtcs.2105"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/j.ipl.2008.10.015","article-title":"Nearly tight bounds on the number of Hamiltonian circuits of the hypercube and generalizations","volume":"109","author":"Feder","year":"2009","journal-title":"Inf. Process. Lett."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"2053","DOI":"10.1016\/j.disc.2005.12.050","article-title":"Spanning multi-paths in hypercubes","volume":"307","author":"Caha","year":"2007","journal-title":"Discrete Math."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1137\/S0895480103432805","article-title":"Hamiltonian cycles with prescribed edges in hypercubes","volume":"19","year":"2005","journal-title":"SIAM J. Discrete Math."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1100","DOI":"10.1137\/070697288","article-title":"Connectivity of matching graph of hypercube","volume":"23","author":"Fink","year":"2009","journal-title":"SIAM J. Discrete Math."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"055201","DOI":"10.1088\/1402-4896\/adc3d2","article-title":"Characteristics and eigenvalues of the newly defined Ala graph","volume":"100","author":"Alaeiyan","year":"2025","journal-title":"Phys. Scr."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1137\/0406012","article-title":"Hamilton cycles that extend transposition matchings in Cayley graphs of Sn","volume":"6","author":"Ruskey","year":"1993","journal-title":"Siam J. Discret. Math."},{"key":"ref_9","first-page":"87","article-title":"Matchings and Hamiltonian cycles on hypercubes","volume":"16","author":"Kreweras","year":"1996","journal-title":"Bull. Inst. Combin. Appl."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1074","DOI":"10.1016\/j.jctb.2007.02.007","article-title":"Perfect matchings extend to Hamilton cycles in hypercubes","volume":"97","author":"Fink","year":"2007","journal-title":"J. Comb. Theory, Ser. B"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1624","DOI":"10.1016\/j.ejc.2009.03.007","article-title":"Matching graphs of hypercubes and complete bipartite graphs","volume":"30","author":"Fink","year":"2009","journal-title":"Eur. J. Comb."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1711","DOI":"10.1016\/j.disc.2008.02.013","article-title":"Perfect matchings extending on subcubes to Hamiltonian cycles of hypercubes","volume":"309","author":"Gregor","year":"2009","journal-title":"Discret. Math."},{"key":"ref_13","first-page":"123","article-title":"Gray codes avoiding matchings","volume":"11","author":"Dimitrov","year":"2009","journal-title":"Discrete Math. Theoret. Comput. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"217","DOI":"10.7151\/dmgt.2010","article-title":"Matchings extend to Hamiltonian cycles in 5-cube","volume":"38","author":"Wang","year":"2018","journal-title":"Discuss. Math. Graph Theory"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"249","DOI":"10.21136\/MB.1997.126151","article-title":"On r-extendability of the hypercube Qn","volume":"122","author":"Limaye","year":"1997","journal-title":"Math. Bohem."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1539","DOI":"10.1137\/080732687","article-title":"Matching extendability in hypercubes","volume":"23","author":"Jennifer","year":"2009","journal-title":"SIAM J. Discret. Math."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/s00373-015-1533-6","article-title":"Small matchings extend to Hamiltonian cycles in hypercubes","volume":"32","author":"Fan","year":"2016","journal-title":"Graphs Comb."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1002\/jgt.22371","article-title":"Gray codes extending quadratic matchings","volume":"90","year":"2019","journal-title":"J. Graph Theory"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Bondy, J., and Murty, U. (1976). Graph Theory with Applications, Macmillan Press.","DOI":"10.1007\/978-1-349-03521-2"},{"key":"ref_20","first-page":"269","article-title":"Two types of matchings extend to Hamiltonian cycles in hypercubes","volume":"118","author":"Wang","year":"2015","journal-title":"ARS Combin."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"5237","DOI":"10.1051\/ro\/2024210","article-title":"A kind of matchings extend to Hamiltonian cycles in hypercubes","volume":"58","author":"Wang","year":"2024","journal-title":"Rairo-Oper. Res."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/17\/7\/995\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T17:57:47Z","timestamp":1760032667000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/17\/7\/995"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,24]]},"references-count":21,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2025,7]]}},"alternative-id":["sym17070995"],"URL":"https:\/\/doi.org\/10.3390\/sym17070995","relation":{},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,24]]}}}