## 4 Properties of \(\gamma\)-Graphs of Trees
### The Structure of Stems in 4-Cycles  
Finally, we explore some properties of stems in a 4-cycle in the \(\gamma\)-graph of a tree. In particular we focus on the structure of the dominating set associated with the stem and the corresponding structure of the \(\gamma\)-graph. We first obtain the following Lemma. Lemma 13: _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 every vertex in \(S\) has an \(S\)-external private neighbour, then \(k=1\)._  
Proof. : By Lemma 6, there exists vertices \(x\in S\) and \(y_{1},y_{2},\ldots,y_{k}\in V(T)-S\) so that \(x\sim y_{i}\) and \(L_{i}=(S-\{x\})\cup\{y_{i}\}\) for \(i=1,2,\ldots k\). By Lemma 4, every vertex except \(y_{j}\) in \(L_{j}\) has at least two \(L_{j}\)-external private neighbours, so by Lemma 5, every vertex other than \(x\) in \(S\) has at least one \(S\)-external private neighbour. It follows that \(x\) has an \(S\)-external private neighbour and therefore by Observation 3, \(k=1\). Proposition 6: _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)\geq 3\), then \(G^{\prime}\) is a Cartesian product graph if and only if every vertex in \(S\) has an \(S\)-external private neighbour._  
Proof. : By Lemma 6, there exists vertices \(x\in S\) and \(y_{1},y_{2},\ldots,y_{k}\in V(T)-S\) so that \(x\sim y_{i}\) and \(L_{i}=(S-\{x\})\cup\{y_{i}\}\) for \(i=1,2,\ldots k\). By Lemma 4, every vertex except \(y_{j}\) in \(L_{j}\) has at least two \(L_{j}\)-external private neighbours, so by Lemma 5, every vertex other than \(x\) in \(S\) has at least one \(S\)-external private neighbour. Let \(\{x\}\cup Z\) be the set of vertices that can be swapped from \(S\). If \(z\in Z\), then \(z\) has two \(L_{j}\)-external private neighbours, but has at exactly one \(S\)-external private neighbour. Therefore, each \(z\in Z\) has a distinct common neighbour with \(x\) which is not adjacent to any vertex of \(S-\{x,z\}\). Furthermore, rooting \(T\) at \(x\), each \(z\in Z\) is in a distinct branch. By Observation 1, each \(z\in Z\) is associated with exactly one edge incident with \(S\) in \(G^{\prime}\). Hence as \(\deg_{G^{\prime}}(S)\geq 3\), if \(x\) has no \(S\)-external private neighbour, then \(|Z|\geq 2\). Suppose \(G^{\prime}=G_{1}\,\square\,G_{2}\) is a Cartesian product graph but some vertex in \(S\) has no \(S\)-external private neighbour. Then \(x\) has no \(S\)-external private neighbour and it follows that \(|Z|\geq 2\). For \(i\in\{1,2\}\), let \(z_{i}\) be distinct elements of \(Z\) and let \(w_{i}\) be common neighbour of \(x\) and \(z_{i}\) which is not adjacent to any vertex of \(S-\{x,z_{i}\}\). For a given \(i\), \(U_{i}=(S-\{x\})\cup\{w_{i}\}\) is a \(\gamma\)-set of \(T\) in \(G^{\prime}\) adjacent to \(S\). Let \(e_{i}=SU_{i}\). If \(e_{1}\) is associated with an edge in \(G_{1}\) and \(e_{2}\) is associated with an edge in \(G_{2}\), note that \(e_{1}\,\square\,e_{2}\) is a 4-cycle which is a subgraph of \(G^{\prime}\). This contradicts that the vertices \(a\) and \(b\) in the statement of Proposition 2 are unique. Hence we may assume each \(e_{i}\) is in \(G_{1}\). By Theorem 2, \(G_{1}\) and \(G_{2}\) are connected. Then there exists an edge \(e\) incident with \(S\) associated with an edge in \(G_{2}\). Then for each \(i\), \(e_{i}\,\square\,e\) is 4-cycle which is a subgraph of \(G^{\prime}\). By Proposition 2, \(e\) swaps of some \(z\in Z\), \(z=z_{1}\). Hence if \(e=SW\), there exists a vertex \(a\
otin S\) so that \(a\sim z_{1}\) and \(W=(S-\{z_{1}\})\cup\{a\}\) is \(\gamma\)-set of \(T\) in \(G^{\prime}\). It follows from Observation 1 and that \(z_{1}\) has an \(S\)-external private neighbour that \(a\
otin w_{1}\). Consider the 4-cycle \(e_{2}\,\square\,e\).