Reconfiguring Minimum Dominating Sets in Trees
Vol. 24, no. 1, pp. 47-61, 2020. Regular paper.
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.
Submitted: May 2019.
Reviewed: August 2019.
Revised: September 2019.
Reviewed: December 2019.
Revised: January 2020.
Accepted: January 2020.
Final: January 2020.
Published: February 2020.
Communicated by Anna Lubiw
article (PDF)