On Shortest Path, BFS- and DFS-Tree Graphs

Abstract

Flip graphs encode the structure of feasible transformations between combinatorial objects, making them a fundamental tool in reconfiguration problems. Tree graphs, which are flip graphs whose nodes represent the spanning trees of a graph, have received significant attention due to their algorithmic and structural properties.
In this paper, we introduce new variations of tree graphs by restricting the spanning trees to shortest path trees, breadth-first search (BFS) trees, and depth-first search (DFS) trees. We prove that shortest path tree graphs are hamiltonian. Given any graph $G$, we present an algorithm that finds a hamiltonian cycle in its corresponding shortest path tree graph. We show that BFS-tree graphs and DFS-tree graphs are not necessarily connected. We establish some necessary conditions for the connectivity of BFS-tree and DFS-tree graphs. We provide an optimal linear-time algorithm for reconfiguration in shortest path tree graphs. Finally, we derive some bounds on the chromatic numbers of these new variations of tree graphs.