## 4 Properties of \(\gamma\)-Graphs of Trees
### The Structure of Stems in 4-Cycles
We conclude by providing two additional tools to determine if graphs with stems are \(\gamma\)-graphs. **Lemma 14**. : _Let \(G\) be a \(\gamma\)-graph of a tree \(T\), \(S\) be a stem of \(G\), \(L_{1},L_{2},\ldots,L_{k}\) be the leaves of \(S\), and \(G^{\prime}=G-\{L_{1},L_{2},\ldots,L_{k}\}\). If \(\deg_{G^{\prime}}(S)>2\alpha^{\dagger}(G^{\prime},S)\), then \(G^{\prime}\) is a Cartesian product graph._  
Proof. : Suppose \(G^{\prime}\) is not a Cartesian product graph. If \(L_{j}=(S-\{x\})\cup\{y_{j}\}\) (Lemma 6), then it follows from Proposition 6, that \(x\) has no \(S\)-external private neighbour. By Proposition 2 at \(x\) can be swapped from \(S\) in \(G^{\prime}\) at most \(\alpha^{\dagger}(G^{\prime},S)\) times, so \(\deg_{T}(x)\leq k+\alpha^{\dagger}(G^{\prime},S)\). Let \(\{x\}\cup Z\) be the set of vertices that can be swapped from \(S\). Then \(\deg_{G^{\prime}}(S)=(deg_{T}(x)-k)+|Z|\). It can be shown, as in previous proofs, each \(z\in Z\) has a distinct common neighbour with \(x\) in \(G^{\prime}\), so \(|Z|\leq(deg_{T}(x)-k)\) and hence \(\deg_{G^{\prime}}(S)\leq 2(deg_{T}(x)-k)\leq 2\alpha^{\dagger}(G^{\prime},S)\), which is a contradiction. Hence, \(G^{\prime}\) is a Cartesian product graph. **Proposition 8**. : _Let \(G\) be the \(\gamma\)-graph of a tree \(T\), \(S\) be a stem of \(G\), \(L_{1},L_{2},\ldots,L_{k}\) be the leaves of \(S\), and \(G^{\prime}=G-\{L_{1},L_{2},\ldots,L_{k}\}\). If \(\deg_{G^{\prime}}(S)=2\), \(S\) is in the 4-cycle \(PQRS\), and every vertex adjacent to \(Q\) is in a 4-cycle with \(P\) or \(R\), then \(G^{\prime}\) is a Cartesian product graph._  
Proof. : Suppose \(G^{\prime}\) is not a Cartesian product. Let \(L_{j}=(S-\{x\})\cup\{y_{j}\}\) (Lemma 6), then it follows from Proposition 6, that \(x\) has no \(S\)-external private neighbour. It follows from Lemma 14, that \(\deg_{G^{\prime}}(S)\leq 2\alpha^{\dagger}(G^{\prime},S)\) and hence \(\alpha^{\dagger}(G^{\prime},S)=1\). Rooting \(T\) at \(x\) each descendant of \(y_{j}\) in \(S\) has at least two \(L_{j}\)-external private neighbours, each descendant of \(y_{j}\) in \(S\) is in every \(\gamma\)-set of \(T\). Delete each \(y_{j}\) from \(T\) and let \(T^{\prime}\) be the component containing \(x\). Then \(G^{\prime}\cong T^{\prime}(\gamma)\). As \(\alpha^{\dagger}(G^{\prime},S)=1\), it follows from Proposition 2 only one swap in \(G^{\prime}\) can use \(x\), so \(\deg_{T^{\prime}}(x)=1\). If \(z\) is the other swap possible from \(S\), then \(x\) and \(z\) have a common neighbour \(w\), and \(pn(z,S)=\{v\}\). Hence we may assume without loss of generality that the neighbours of \(S\) are \(P=(S-\{z\})\cup\{v\}\) and \(R=(S-\{x\})\cup\{w\}\). By Proposition 2, \(Q=(S-\{x,z\})\cup\{w,v\}\). Let \(T_{1}\) be the component of \(T^{\prime}-zw\) containing \(w\) and \(T_{2}\) be the component of \(T^{\prime}-zw\) containing \(z\). Let \(T_{1}+T_{2}\) be the disjoint union of \(T_{1}\) and \(T_{2}\). Suppose \(A\) is a \(\gamma\)-set \(T^{\prime}\) but not a \(\gamma\)-set of \(T_{1}+T_{2}\). If \(w\
ot\in N_{T_{1}+T_{2}}[A]\), then \(x\
ot\in N_{T^{\prime}}[A]\), which contradicts that \(A\) is a \(\gamma\)-set of \(T^{\prime}\). Hence, \(N_{T_{1}+T_{2}}[A]=V(T^{\prime})-\{z\}\) and \(w\in A\). As \(v\) is dominated by \(A\), but \(v\) is not in \(A\), there exists a neighbour of \(v\), \(t\in A\). As \(pn(z,S)=\{v\}\), it follows that \(O=(S-\{x,z\})\cup\{w,t\}\) is a \(\gamma\)-set of \(T^{\prime}\). Hence, \(O=(Q-\{v\})\cup\{t\}\) is a \(\gamma\)-set of \(T^{\prime}\) with \(v\sim t\) and \(z\in pn(w,O)\) and therefore \(O\) is adjacent to \(Q\). However, by Proposition 2, \(O\) does not form a 4-cycle with \(P\), as \((O-\{w\})\cup\{x\}\) is not a \(\gamma\)-set of \(T^{\prime}\), and \(O\) does not form a 4-cycle with \(R\), as \((R-\{v\})\cup\{t\}\) is not a minimal dominating set (\(v\
ot\in R\)). Hence, every \(\gamma\)-set of \(T^{\prime}\) is a \(\gamma\)-set of \(T_{1}+T_{2}\). Further, since \(x\) or \(w\) is in every \(\gamma\)-set in \(G^{\prime}\), no swap in \(T^{\prime}\) uses the edge \(zw\).