## 4 Properties of \(\gamma\)-Graphs of Trees
### The Structure of Stems in 4-Cycles
By Proposition 2, \(V=S-\{x,z_{1}\}\cup\{w_{2},a\}\) is a \(\gamma\)-set of \(T\) with no neighbour of \(w_{1}\), a contradiction. Hence vertex in \(S\) has an \(S\)-external private neighbour. Conversely, suppose every vertex in \(S\) has an \(S\)-external private neighbour. By Lemma 13, \(k=1\) and it follows that, \(y_{1}\) is the \(S\)-external private neighbour of \(x\). Rooting \(T\) at \(x\), every descendant of \(y_{1}\) in \(L_{1}\) has at least two \(L_{1}\)-external private neighbours. Hence every descendant of \(y_{1}\) in \(S\) has at least two \(S\)-external private neighbours. By Lemma 8, the only dominating set of \(T\) containing \(y_{1}\) is \(L_{1}\) and hence for every \(\gamma\)-set \(D\
eq L_{1}\) of \(T\) every descendant of \(y_{1}\) in \(S\) has at least two \(D\)-external private neighbours and cannot be swapped. It follows that \(x\) is in every \(\gamma\)-set which corresponds to a vertex in \(G^{\prime}\). Then \(|Z|=\deg_{G^{\prime}}(S)\geq 3\geq 2\), and each \(z_{i}\in Z\) has a distinct common neighbour with \(x\). Each \(z_{i}\) is in a distinct branch of \(T\), and swaps occur in each such branch independently. Hence, \(G^{\prime}\) is a Cartesian product graph. Note that in the proof of the converse of the previous proposition the line, \(\deg_{G^{\prime}}(S)\geq 3\), \(|Z|=\deg_{G^{\prime}}(S)\geq 3\geq 2\). For the result we require that \(|Z|\geq 2\). Hence when a stem in the \(\gamma\)-graph has fewer non-leaf neighbours, we obtain the result in one direction. **Proposition 7**. : _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 2\), and every vertex in \(S\) has an \(S\)-external private neighbour, then \(G^{\prime}\) is a Cartesian product graph._  
We immediately obtain the following result demonstrating where leaves cannot be attached to Cartesian product graphs. Recall the vertices of the graph \(G_{1}\,\square\,\,G_{2}\,\square\cdots\square\,\,G_{n}\) are ordered \(n\)-tuples. In particular, each vertex \(v\in V(G_{1}\,\square\,\,G_{2}\,\square\cdots\square\,\,G_{n})\) can be written in the form \(v=(v_{1},v_{2},\ldots,v_{n})\), where \(v_{i}\in V(G_{i})\) for \(i=1,2,\ldots,n\). **Corollary 4**. : _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\), \(G^{\prime}=G_{1}\,\square\,\,G_{2}\,\square\cdots\square\,\,G_{n}\), where each \(G_{i}\) is 'prime', and \(S=(V_{1},V_{2},\ldots,V_{n})\), then each \(V_{i}\) is a leaf in \(G_{i}\)._  
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 Proposition 6, \(x\) has an \(S\)-external private neighbour and it follows from Lemma 13, that \(k=1\) and \(y_{1}\) is the only \(S\)-external private neighbour of \(x\). Rooting \(T\) at \(x\), and noting every descendant of \(y_{1}\) in \(L_{1}\) has at least two \(L_{1}\)-external private neighbours, it follows that \(x\) is in every \(\gamma\)-set which corresponds to a vertex in \(G^{\prime}\). Recalling that \(T\) is rooted at \(x\) let \(Z\) be the set of vertices that can be swapped from \(S\) in \(G^{\prime}\); each \(z\in Z\) has a distinct common neighbour with \(x\) and each \(z\in Z\) is in a distinct branch of \(T\). Swaps occur in each such branch independently. Therefore, if \(G^{\prime}=G_{1}\,\square\,G_{2}\,\square\cdots\square\,G_{n}\), where each \(G_{i}\) is 'prime', then without loss of generality each \(z\in Z\) swap occurs in a different \(G_{i}\). Hence \(V_{i}\) is a leaf in \(G_{i}\) as only one swap associated with an edge in \(G_{i}\) can occur. Let \(\alpha^{\dagger}(G,v)\) denote the maximum number of edges incident with \(v\) with no pair of edges part of the same 4-cycle.