What type of study is this?

This is a Quantitative Study study.

September 17, 2025

Matchings in Hypercubes Extend to Long Cycles

Key Points

Every matching in the hypercube graph can be extended to visit at least two-thirds of the vertices.
This finding supports the Ruskey–Savage conjecture regarding Hamilton cycles for hypercubes.
The proof applies to all hypercube dimensions starting from d equals two.
These results advance understanding of cycle structures in high-dimensional graphs.

Abstract

. The \ (d\) -dimensional hypercube graph \ (Qd\) has as vertices all subsets of \ (\1, , d\\), and an edge between any two sets that differ in a single element. The Ruskey–Savage conjecture asserts that every matching of \ (Qd\), \ (d 2\), can be extended to a Hamilton cycle, i. e. , to a cycle that visits every vertex exactly once. We prove that every matching of \ (Qd\), \ (d 2\), can be extended to a cycle that visits at least a \ (2/3\) -fraction of all vertices. KeywordshypercubecyclematchingMSC codes05C3805C7005C45

Mark Helpful

Bookmark

Relay