## 3 \(\gamma\)-Trees of Trees
Note that for \(i=1,2\), \(pn(S,x_{i})=pn(L_{i},y_{i})\subseteq\{x_{i},y_{i}\}\). As each \(x_{i}\) has an \(S\)-external private neighbour, \(y_{i}\) is an \(S\)-private neighbour of \(x_{i}\). Hence for \(i=1,2\), \(x_{i}\) may only swap with \(y_{i}\). Furthermore as \(y_{i}\) is the only vertex in \(L_{i}\) with fewer than two \(L_{i}\)-external private neighbours, \(x_{1}\) and \(x_{2}\) have only one common neighbour, \(z_{12}\), and since \(T\) has no cycles, it follows that \(x_{1}\) and \(x_{2}\) are the only vertices in \(S\) with fewer than two \(S\)-external private neighbours. Thus, \(S\), \(L_{i}\), and \(L_{j}\) are the only \(\gamma\)-sets of \(T\), contradicting that \(S\) has degree at least three. Hence, \(|X|=1\), which completes the proof. Our next step is to show the graph \(H\), pictured in Figure 1, is not a \(\gamma\)-graph of a tree. Lemma 7: _No tree has \(H\) as its \(\gamma\)-graph._  
Proof: Let \(H\) be labeled as in Figure 1 and suppose \(H\) is the \(\gamma\)-graph of a tree \(T\). By Lemma 6, there exists vertices \(x\in S\) and \(w\in R\) so that \(L_{i}=(S-\{x\})\cup\{y_{i}\}\) and \(M_{i}=(R-\{w\})\cup\{z_{i}\}\) where \(y_{1},y_{2}\in N(x)\) and \(z_{1},z_{2}\in N(w)\). Further there exists \(u\in S\) so that \(R=(S-\{u\})\cup\{v\}\) with \(u\sim v\). By Observation 3, \(x\) has no \(S\)-external private neighbours and \(w\) has no \(R\)-external private neighbours. Suppose first \(x\in R\). Then \(x\
eq u\) and by Lemma 5, \(x\) has at most one \(R\)-external private neighbour. Hence, there exists a vertex \(y^{\prime}\in N(x)\) such that \(Q:=(R-\{x\})\cup\{y^{\prime}\}\) is a \(\gamma\)-set of \(T\). As \(x\
eq u\) and \(R\) has only three neighbours, it follows that \(Q\in\{M_{1},M_{2}\}\) and therefore \(x=w\). By Observation 2, \(N(x)=\{y_{1},y_{2}\}\) and \(N(w)=\{z_{1},z_{2}\}\) and therefore \(\{y_{1},y_{2}\}=\{z_{1},z_{2}\}\). Without loss of generality \(y_{1}=z_{1}\). Then \(M_{1}=L_{1}-\{u\}\cup\{v\}\). Thus, \(L_{1}\) and \(M_{1}\) are neighbours in \(H\), which is a contradiction. Hence it must be that \(x\
otin R\). By symmetry, \(w\
otin S\). It follows that \(x=u\) and \(w=v\). In particular, \(x\sim w\). But as \(w\) has no \(R\)-external private neighbours, it is a self private neighbour in \(R\), and hence must be an external private neighbour of \(x\) in \(S\). But \(x\) has no \(S\)-external private neighbours, which is a contradiction. The result follows. We now show that if a graph is a \(\gamma\)-graph of a tree, then deleting leaves produces graphs that must also be \(\gamma\)-graphs of trees. In particular, if a tree is a \(\gamma\)-graph of a tree, then all subtrees are also \(\gamma\)-graphs of trees. Lemma 8: _If \(G\) is a \(\gamma\)-graph of a tree \(T\), \(D\) is a leaf of \(G\) and \(x\in D\) has fewer than two \(D\)-external private neighbours, then \(D\) is the unique \(\gamma\)-set of \(T\) containing \(x\)._  
Proof: Consider \(T^{\prime}\) a component of \(T-N[x]\). Then \(D\cap V(T^{\prime})\) is clearly a dominating set of \(T^{\prime}\). If \(D\cap V(T^{\prime})\) is not also a \(\gamma\)-set of \(T^{\prime}\), then \(D\) is not minimal. Hence \(D\cap V(T^{\prime})\) is a \(\gamma\)-set of \(T^{\prime}\) and since each vertex of \(D-\{x\}\) has at least two \(D\)-external private neighbours, \(D\cap V(T^{\prime})\) has no neighbours in \(T^{\prime}(\gamma)\). It follows from Theorem 2 that \(D\cap V(T^{\prime})\) is the only \(\gamma\)-set of \(T^{\prime}\). As \(T\) is a tree, the vertices  
Figure 1: The graph \(H\). in \(N(x)\) are adjacent to at most one vertex in \(T^{\prime}\). Recall each vertex of \(D\cap V(T^{\prime})\) has at least two \(D\)-external private neighbours. Let \(E\) be a \(\gamma\)-set of \(T\) containing \(x\). Then \(E\cap V(T^{\prime})\) must contain at least \(|D\cap V(T^{\prime})|\) vertices. Since \(T^{\prime}\) was arbitrary, \(|D|=|E|=\gamma(T)\) and \(|D\cap V(T^{\prime})|=|E\cap V(T^{\prime})|\), the set \(E\) has at most one vertex in \(N[x]\), namely \(x\).