Matchings in hypercubes extend to long cycles
| Autor: | Fink, Jiří, Mütze, Torsten |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | The $d$-dimensional hypercube graph $Q_d$ has as vertices all subsets of $\{1,\ldots,d\}$, and an edge between any two sets that differ in a single element. The Ruskey-Savage conjecture asserts that every matching of $Q_d$, $d\ge 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 $Q_d$, $d\ge 2$, can be extended to a cycle that visits at least a $2/3$-fraction of all vertices. |
| Databáze: | arXiv |
| Externí odkaz: |
|