\(\gamma\)-graphs of trees (Q2005551)

Summary: For a graph \(G = (V, E)\), the \(\gamma\)-graph of \(G\), denoted \(G(\gamma) = (V(\gamma), E(\gamma))\), is the graph whose vertex set is the collection of minimum dominating sets, or \(\gamma\)-sets of \(G\), and two \(\gamma\)-sets are adjacent in \(G(\gamma)\) if they differ by a single vertex and the two different vertices are adjacent in \(G\). In this paper, we consider \(\gamma\)-graphs of trees. We develop an algorithm for determining the \(\gamma\)-graph of a tree, characterize which trees are \(\gamma\)-graphs of trees, and further comment on the structure of \(\gamma\)-graphs of trees and its connections with Cartesian product graphs, the set of graphs which can be obtained from the Cartesian product of graphs of order at least two.