## 1 Introduction
Let \(D_{i}\) be the set of minimum dominating sets of subtree \(T_{i}\) and let \(T_{i}^{x_{i}}(\gamma)\) be the \(\gamma\)-graph of subtree \(T_{i}\) using only those \(\gamma\)-sets of \(D_{i}\) that do not contain \(x_{i}\). Then_  
\[T(\gamma)=T_{1}(\gamma)\,\square\,T_{2}(\gamma)\,\square\,\cdots\square\,T_{ k}(\gamma)-(T_{1}^{x_{1}}(\gamma)\,\square\,T_{2}^{x_{2}}(\gamma)\,\square\, \cdots\square\,T_{k}^{x_{k}}(\gamma)).\]  
**Theorem 2**. : _[_4_]_ _The \(\gamma\)-graph \(T(\gamma)\) of every tree \(T\) is a connected graph._  
**Theorem 3**. : _[_4_]_ _For any tree \(T\), \(T(\gamma)\) is \(C_{n}\)-free, for any odd \(n\geq 3\). [That is, \(T(\gamma)\) is bipartite. ]_  
The main objective of this paper is the investigation of open question 4. In Section 2, we develop a method for constructing the \(\gamma\)-graph of a tree. In Section 3, we characterize those trees which are \(\gamma\)-graphs of trees. Finally, in Section 4, we state some further results for graphs which are \(\gamma\)-graphs of trees. The following observations are used, frequently without reference, throughout the paper. **Observation 1**. : _If \(D_{1}\) and \(D_{2}=(D_{1}-\{u\})\cup\{v\}\) with \(u\sim v\) are two distinct \(\gamma\)-sets of a tree, then \(pn(D_{1},u)=pn(D_{2},v)\subseteq\{u,v\}\)._  
**Observation 2**. : _If \(u\in D\) is such that \(pn(D,u)=\{u\}\), then for each \(v\in N(u)\), we have that \(D\) is adjacent to \(D_{v}=(D-\{u\})\cup\{v\}\)._  
**Observation 3**. : _If \(D_{1}\), \(D_{2}=(D_{1}-\{u\})\cup\{v\}\) and \(D_{3}=(D_{1}-\{u\})\cup\{w\}\) with \(v,w\in N(u)\) are three distinct gamma-sets of a tree, then \(pn(D_{1},u)=pn(D_{2},v)=pn(D_{3},w)=\{u\}\)._  
Note that Observations 1 and 3 do not hold for general graphs. **2. Computing \(\gamma\)-Graphs of Trees**  
While [PERSON] et al. [4] developed a method to determine the \(\gamma\)-graphs of trees that contain a vertex not appearing in any \(\gamma\)-set (Theorem 1), there are trees for which every vertex appears in some \(\gamma\)-set. We present a general algorithm to determine the \(\gamma\)-graph of a tree. We first state the following results of [PERSON], [PERSON], and [PERSON] [3] which will aid in verifying the algorithm. If \(D\) is a \(\gamma\)-set of a rooted tree \((T,c)\), then the _depth_ of \(D\), denoted \(dp_{T}(D)\) (referred to as the height of \(D\) in [3]), is \(\sum_{x\in D}d(x,c)\). Define \(D\) to be a _higher_\(\gamma\)-set than \(F\) if \(dp_{T}(D)<dp_{T}(F)\) and \(D\) to be a _highest_\(\gamma\)-_set_ if \(dp_{T}(D)\leq dp_{T}(F)\) for all \(\gamma\)-sets \(F\) of \(T\). That is the minimum depth is equal to the greatest height. Lemma 1: _[_3_]_ _A \(\gamma\)-set \(D\) is a highest \(\gamma\)-set of a tree \(T\) rooted at a vertex \(c\) if and only if every \(x\in D-\{c\}\) has a child \(y\in pn(x,D)\)._  
Theorem 4.1: _[_3_]_ _Let \(T\) be a tree rooted at a vertex \(c\). Then \(T\) has a unique highest \(\gamma\)-set._  
The algorithm DOMSET, developed by [PERSON], [PERSON], and [PERSON] [1] finds a minimum dominating set of a tree in linear time. We demonstrate that with a slight modification to the algorithm not affecting the run time, i.e., we exclude the root from being an eligible end vertex, the algorithm finds the highest minimum dominating set of a rooted tree. Theorem 4.2: _Let \(T\) be a tree rooted at a vertex \(c\). The output, \(S\), of \(\operatorname{HIGHEST}(T,c)\) (see Algorithm 1) is the highest \(\gamma\)-set of \(T\)._  
```
1:procedure\(\operatorname{HIGHEST}(T,c)\)
2: Set \(S\leftarrow\emptyset\); \(G\gets T\); label each vertex of \(T\) as bound. 3:while\(G\) has an endvertex \(v\
eq c\) adjacent to a vertex \(u\)do
4:if\(v\) is freethen
5:\(G\gets G-v\). 6:elseif\(v\) is boundthen
7: Relabel \(u\) as required;
8:\(G\gets G-v\). 9:elseif\(v\) is requiredthen
10:\(S\gets S\cup\{v\}\);
11: If \(u\) is bound then relabel \(u\) as free;
12:\(G\gets G-v\). 13:endif
14:endwhile
15:if\(c\) is not freethen
16:\(S\gets S\cup\{c\}\).