Reconfiguring Minimum Dominating Sets: The γ-Graph of a Tree

Abstract

We consider γ-graphs, which are reconfiguration graphs of the minimum dominating sets of a graph G. We answer three open questions about γ- graphs of trees by providing upper bounds on the maximum degree, the diameter, and the number of minimum dominating sets. The latter gives an upper bound on the order of the γ-graph.

Keywords

• domination
• reconfiguration
• 05c69