Reconfiguring Minimum Dominating Sets in Trees - Lemańska, Magdalena; Żyliński, Paweł (Journal of Graph Algorithms and Applications, 2020)
We provide tight bounds on the diameter of $γ$-graphs, which are reconfiguration graphs of the minimum dominating sets of a graph $G$. In particular, we prove that for any tree $T$ of order $n \ge 3$, the diameter of its $γ$-graph is at most $n/2$ in the single vertex replacement adjacency model, whereas in the slide adjacency model, it is at most $2(n-1)/3$. Our proof is constructive, leading to a simple linear-time algorithm for determining the optimal sequence of ``moves'' between two minimum dominating sets of a tree.