Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00517
Reconfiguring Minimum Dominating Sets in Trees
Vol. 24, no. 1, pp. 4761, 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(n1)/3$. Our proof is constructive, leading to a simple lineartime 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
