Reconfiguring Minimum Dominating Sets in Trees

Abstract

We provide tight bounds on the diameter of $\gamma$-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 $\gamma$-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.