Matchings with Five Directions in Hypercubes Extend to Hamilton Cycles and Paths with Prescribed Ends
摘要
The n-dimensional hypercube graph \(Q_n\) has vertices representing all binary strings of length n, with edges between strings differing in exactly one bit position. The Ruskey-Savage conjecture states that every matching of \(Q_n\) can be extended into a Hamilton cycle. We prove that matchings of \(Q_n\) containing edges spanning at most \(d = 5\) directions can be extended into a Hamilton cycle. We also characterize when these matchings spanning at 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 \le n\) , assuming certain extension properties hold in \(Q_d\) , which we verified computationally for \(d = 5\) .