## 4 Properties of \(\gamma\)-Graphs of Trees
### Cartesian Product and \(\gamma\)-Graphs of Trees  
Every edge in the Cartesian product of two connected graphs of order at least two is in a 4-cycle. Theorem 1 highlights one aspect of the connection between \(\gamma\)-graphs and the Cartesian product. When movement of the dominating set in one part of a graph has no effect on movement of the dominating set in another part of the graph, the Cartesian product frequently arises. In this section we exploit this connection and establish that the Cartesian product can both decompose \(\gamma\)-graphs of trees into smaller \(\gamma\)-graphs of trees and be used to combine \(\gamma\)-graphs of trees to discover other \(\gamma\)-graphs of trees. We first consider _Cartesian product graphs_, the set of graphs which can be obtained from the Cartesian product of graphs of order at least two. [PERSON] [7] and [PERSON] [9] independently demonstrated a prime factorization of graphs, analogous to the Fundamental Theorem of Arithmetic. **Theorem 11**: _[_7; 9_]_ _All finite connected graphs have a unique prime factorization with respect to Cartesian multiplication._  
We show that if \(G\) is a 'composite' graph, then each of its prime factors are \(\gamma\)-graphs of trees if and only if \(G\) is also the \(\gamma\)-graph of a tree. Hence, to characterize \(\gamma\)-graphs of trees, we need only consider 'prime' graphs under Cartesian multiplication. The proof in one direction is technical and so we first provide an example to demonstrate the proof. We require a definition. Let \(T\) be a tree and consider an edge \(e=D_{1}D_{2}\) of \(T(\gamma)\), where \(D_{1}\) and \(D_{2}\) are \(\gamma\)-sets of \(T\). Define \(sw(e)=\{x,y\}\), the unique vertices \(x\) and \(y\) so that \(D_{2}=(D_{1}-\{x\})\cup\{y\}\). Consider \(C_{4}\,\square\,P_{5}\), shown in Figure 4, is the \(\gamma\)-graph of the tree \(T\) shown in Figure 5 and the edge \(e=U_{1}U_{2}\) in \(C_{4}\). The edges in \(C_{4}\,\square\,P_{5}\) associated with \(e\) are labelled \(e_{1}\), \(e_{2}\), \(e_{3}\), \(e_{4}\) and \(e_{5}\). Recall the two vertices incident with \(e_{1}\), namely \(D_{1}=(U_{1},V_{1})\) and \(D_{2}=(U_{2},V_{1})\) in \(C_{4}\,\square\,P_{5}\) are equated with \(\gamma\)-sets of \(T\) and since \(e_{1}\) is an edge in the \(T(\gamma)\), there exists vertices \(x,y\in V(T)\) so that \(D_{2}=(D_{1}-\{x\})\cup\{y\}\). Hence \(sw(e_{1})=\{x,y\}\). By Proposition 2, it is also the case that \(sw(e_{2})=\{x,y\}\) and if \(e^{\prime}\) is incident with \(e_{1}\), then \(x\
otin sw(e^{\prime})\) and \(y\
otin sw(e^{\prime})\). Repeated applications of Proposition 2 shows that each of \(sw(e_{3})=sw(e_{4})=sw(e_{5})=\{x,y\}\). Furthermore, Proposition 2 implies any edge \(e^{\prime}\) incident with \(e_{1}\), \(e_{2}\), \(e_{3}\), \(e_{4}\), or \(e_{5}\) has the property that \(x\
otin sw(e^{\prime})\) and \(y\
otin sw(e^{\prime})\). Similarly there are vertices \(a,b\in V(T)\) so that \(sw(f_{1})=sw(f_{2})=sw(f_{3})=sw(f_{4})=\{a,b\}\) and that \(a\
otin sw(e^{\prime\prime})\) and \(b\
otin sw(e^{\prime\prime})\) for any edge \(e^{\prime\prime}\) incident with \(f_{1}\), \(f_{2}\), \(f_{3}\), or \(f_{4}\). It follows that \(\{x,y\}\cap\{a,b\}=\emptyset\). More generally let \(E_{1}\) be the set of edges of \(C_{4}\,\square\,P_{5}\) associated with edges of \(C_{4}\,\square\,P_{5}\) associated with edges of \(P_{5}\). Then it follows that  
\[\left(\bigcup_{e^{\prime}\in E_{1}}sw(e^{\prime})\right)\cap\left(\bigcup_{e^{ \prime}\in E_{2}}sw(e^{\prime})\right)=\emptyset.\]  
Now consider the set \(D=(U_{1},V_{1})\) of \(T\) which is indicated in Figure 5, by the vertices in \(D\) being marked with an \(\times\) symbols. Add two leaves to each vertex in \(D\cap\left(\bigcup_{e^{\prime}\in E_{1}}sw(e^{\prime})\right)=\{y,z\}\) to form atree \(T_{2}\). Those vertices in the dominating set associated with edges of \(C_{4}\) must be in every \(\gamma\)-set of \(T_{2}\). It follows that \(T_{2}(\gamma)\) is isomorphic to \(P_{5}\).