$\gamma$-Graphs of Trees

Abstract

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.

22 pages, 3 figures