2025/01/31 by Jiří Fink, Fink, Jiří, Vojtěch Hotmar +1
Computer Science · #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2501.19029
openalex publication_date 2025/01/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The n-dimensional hypercube graph Qn has as vertices all subsets of \1, …, n\, and an edge between any two sets that differ in a single element. The Ruskey-Savage conjecture states that every matching of the n-dimensional hypercube Qn can be extended into a Hamilton cycle. We prove that matchings of Qn containing edges spanning at most d = 5 directions can be extended into a Hamilton cycle. We also characterize when these matchings of most d = 5 directions can be extended into a Hamilton path between two prescribed vertices. Our proofs work for arbitrary d and n where d ≤ n assuming some extension properties hold in Qd which we verified by a computer for d=5.