Pivot Gray code for all spanning trees
Problem 1 · arXiv:2603.28614
Status open high confidence
The question of whether every graph G admits a pivot Gray code on its spanning trees (where consecutive spanning trees share a common endpoint among their differing edges, i.e., the strong revolving door property) remains open as of the source paper's writing. Prior to the source paper, positive answers were known for fan graphs (arXiv:2202.01746, 2022), outerplanar graphs (STACS 2025), and complete graphs (arXiv:2510.22662, SODA 2026); the source paper itself notes these results and states the general problem as open. No post-March 2026 publication resolving the full conjecture was found in a web search.
Reviewer notes. The source paper (2026-03-30) explicitly states that although the reconfiguration graph of spanning trees under edge exchanges is connected for any graph G, it is open whether every graph admits a pivot Gray code. Known positive cases (fan, outerplanar, complete graphs) predate the source paper and are cited therein as background. No follow-up resolving the general problem was found; the conjecture is open with high confidence given the paper's very recent date.
Context
A pivot Gray code for spanning trees requires that consecutive spanning trees differ by an edge exchange sharing a common endpoint (the strong revolving door property). Although the corresponding reconfiguration graph is connected for any graph $G$, it remains open whether all graphs admit such a code. Pivot Gray codes have been constructed for fan graphs and more generally for outerplanar graphs.
Source paper
A Gray code for arborescences of tournaments
Marthe Bonamy, Michael Hoffmann, Clément Legrand-Duchesne, Günter Rote · 2026-03-30
https://arxiv.org/abs/2603.28614
PDF source