Matchings in hypercubes extend to long cycles

DOI10.1137/24M1670093MaRDI QIDQ6918446zbMATH OpenFDO

Authors Jiří Fink, Torsten Mütze

Publication date 10 October 2025

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/24M1670093

zbMATH Keywords

cyclehypercubematchingRuskey-Savage conjecture

Mathematics Subject Classification ID

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

Cites work

• A fast algorithm to generate Beckett-Gray codes
• A new method of generating Hamiltonian cycles on the n-cube
• A Survey of Combinatorial Gray Codes
• Antipodal Gray codes
• Balanced Gray codes
• Binary Gray codes with long bit runs
• Colorings of diagrams of interval orders and \(\alpha\)-sequences of sets
• Combinatorial Gray codes -- an updated survey
• Combining SAT solvers with computer algebra systems to verify combinatorial conjectures
• Embedded paths and cycles in faulty hypercubes
• Extending a perfect matching to a Hamiltonian cycle
• Extending perfect matchings to Gray codes with prescribed ends
• Extensions to 2-factors in bipartite graphs
• Gray codes extending quadratic matchings
• Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of $S_n $
• Hamiltonian cycles in hypercubes with faulty edges
• Hamiltonian Cycles with Prescribed Edges in Hypercubes
• Hamiltonian paths with prescribed edges in hypercubes
• scientific article; zbMATH DE number 5761830 (Why is no real title available?)
• scientific article; zbMATH DE number 3781214 (Why is no real title available?)
• scientific article; zbMATH DE number 3641471 (Why is no real title available?)
• scientific article; zbMATH DE number 888853 (Why is no real title available?)
• Linear time construction of a compressed Gray code
• Long cycles in hypercubes with optimal number of faulty vertices
• Long cycles in the middle two layers of the discrete cube
• Matchings extend into 2-factors in hypercubes
• Matchings in hypercubes extend to long cycles
• Monotone Gray codes and the middle levels problem
• On the Existence of Hamiltonian Circuits in Faulty Hypercubes
• Perfect matchings extend to Hamilton cycles in hypercubes
• Perfect matchings extending on subcubes to Hamiltonian cycles of hypercubes
• Proof of the middle levels conjecture
• Single-Track Gray Codes and Sequences
• Smallest maximal matchings in the graph of the d-dimensional cube
• The Hamilton compression of highly symmetric graphs
• Transition restricted Gray codes
• Two algorithms extending a perfect matching of the hypercube into a Hamiltonian cycle

This page was built for publication: Matchings in hypercubes extend to long cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6918446)