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 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.