A Gray code for arborescences of tournaments
This solves a specific combinatorial problem for tournaments, which is incremental as it builds on prior work in graph theory and Gray codes.
The paper addresses Knuth's question of whether arborescences rooted at a vertex in a directed graph can be listed with consecutive ones differing by only one arc, known as a pivot Gray code, and provides a positive answer for tournaments while exploring conditions where Hamiltonian cycles may not exist in the flip graph.
We consider the following question of Knuth: given a directed graph $G$ and a root $r$, can the arborescences of $G$ rooted in $r$ be listed such that any two consecutive arborescences differ by only one arc? Such an ordering is called a pivot Gray code and can be formulated as a Hamiltonian path in the reconfiguration graph of the arborescences of $G$ under arc flips, also called flip graph of $G$. We give a positive answer for tournaments and explore several conditions showing that the flip graph of a directed graph may contain no Hamiltonian cycles.