Authors:
M. Edwards, G. MacGillivray, S. Nasserasr
Title:
Reconfiguring minimum dominating sets: the γ-graph of a tree
Source:
Discussiones Mathematicae Graph Theory
Received 27.07.2016, Revised 31.01.2017, Accepted 01.02.2017, doi: 10.7151/dmgt.2044

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

Links:
PDF