γ-Graphs of Trees

Abstract

For a graph $G=(V,E)$, the $\gamma$-graph of G, denoted $G\left(\gamma \right)=\left(V\right(\gamma ),E(\gamma \left)\right)$, is the graph whose vertex set is the collection of minimum dominating sets, or $\gamma$-sets of G, and two $\gamma$-sets are adjacent in $G\left(\gamma \right)$ if they differ by a single vertex and the two different vertices are adjacent in G. In this paper, we consider $\gamma$-graphs of trees. We develop an algorithm for determining the $\gamma$-graph of a tree, characterize which trees are $\gamma$-graphs of trees, and further comment on the structure of $\gamma$-graphs of trees and its connections with Cartesian product graphs, the set of graphs which can be obtained from the Cartesian product of graphs of order at least two.

1. Introduction

Let G be a graph and let v be a vertex of G. The open neighbourhood of a vertex v, denoted $N\left(v\right)$, is the set of vertices adjacent to v, and the closed neighbourhood of a vertex v, denoted $N\left[v\right]$, is $N\left(v\right)\cup \left\{v\right\}$. For a subset of vertices S, we say $N\left(S\right)={\cup }_{x\in S}N\left(x\right)$ and $N\left[S\right]=S\cup N\left(S\right)$. A subset of vertices D is a dominating set of G if $N\left[D\right]=V\left(G\right)$, that is, every vertex not in D is adjacent to a vertex in D. The domination number of a graph G, denoted $\gamma \left(G\right)$, is the minimum cardinality of a dominating set of G. A dominating set of minimum cardinality is said to be a γ-set.

For a dominating set D of G and a vertex $x\in D$, the set of D-private neighbours of x, denoted $pn(x,D)$, is $N\left[x\right]-N[D-x]$, that is, the set of vertices in the closed neighbourhood of x and not in the closed neighbourhood of any other vertex in D. If $x\in pn(x,D)$, then x is a D-self private neighbour in D and if $y\ne x$ and $y\in pn(x,D)$, then y is an D-external private neighbour of x in D. If D is a $\gamma$-set, then every vertex in D has a private neighbour.

The γ-graph of a graph G, introduced by Fricke et al. [4], is a graph denoted $G\left(\gamma \right)$, has its vertex set as the $\gamma$-sets of G, and two $\gamma$-sets $D_1$ and $D_2$ are adjacent in $G\left(\gamma \right)$ if there is a vertex $u\in D_1$ and a vertex $v\in D_2$ such that $D_2=(D_1-\left\{u\right\})\cup \left\{v\right\}$ and $uv\in E\left(G\right)$. Starting with $D_1$, we think of making a swap, that is, changing vertex u for v, to form $D_2$. For convenience throughout the paper, we equate each node in $G\left(\gamma \right)$ with its corresponding $\gamma$-set of G. A slightly different model, in which $uv$ need not be an edge in G, was introduced independently by Subramanian and Sridharan [8]; we do not consider this model here. Fricke et al. [4] studied properties of $\gamma$-graphs, and raised the following open questions:

• Is $\Delta \left(T\right(\gamma \left)\right)=O\left(n\right)$ for every tree T of order n?
• Is $\mathrm{diam}\left(T\right(\gamma \left)\right)=O\left(n\right)$ for every tree T of order n?
• Is $\left|V\left(T\left(\gamma \right)\right)\right|\le 2^{\gamma \left(T\right)}$ for every tree T?
• Which graphs are $\gamma$-graphs of trees?
• Which graphs are $\gamma$-graphs? Can you construct a graph H that is not a $\gamma$-graph of any graph G?
• For which graphs G is $G\left(\gamma \right)\cong G$?
• Under what conditions is $G\left(\gamma \right)$ a disconnected graph?

The first three questions were solved by Edwards, MacGillivray, and Nasserasr [3] and the fifth question was answered by Connelly, Hutson, and Hedetneimi [2]; the other three questions remain open. The question of which graphs are $\gamma$-graphs of trees was restated in a recent survey by Mynhardt and Nasserasr [5] as a primary direction of study in this area.

Some $\gamma$-graphs of trees were determined by Fricke et al. [4], as well as a couple of general properties. A stepgrid $SG\left(k\right)$ is the induced subgraph of the $k\times k$ grid graph $P_k\square P_k$ defined as follows: $SG\left(k\right)=\left(V\right(k),E(k\left)\right)$, where

$$\begin{array}{cc}\hfill V\left(k\right)& =\left\{\right(i,j):1\le i,j\le k,i+j\le k+2\},\hfill \\ \hfill E\left(k\right)& =\{((i,j),(i^{\prime },j^{\prime })):i^{\prime }=i,j^{\prime }=j+1;i^{\prime }=i+1,j^{\prime }=j\}.\hfill \end{array}$$

Proposition 1.

[4]

• $K_{1,n}\left(\gamma \right)\cong K_1$.
• For $k\ge 3$, $K_{2,n}\left(\gamma \right)\cong K_{1,2n}$.
• $P_{3k}\left(\gamma \right)\cong K_1$.
• $P_{3k+2}\left(\gamma \right)\cong P_{k+2}$.
• $P_{3k+1}\left(\gamma \right)\cong SG(k+1)$.

Theorem 1.

[4] Let T be a tree, and let $x\in V\left(T\right)$ be a vertex that does not appear in any γ-set of T. Let $T_1,T_2,\dots ,T_k$ be the disjoint subtrees created by deleting x from T, and let $x_i\in T_i$ be the vertex in subtree $T_i$ adjacent to the vertex x. Let $D_i$ be the set of minimum dominating sets of subtree $T_i$ and let $T_i^{x_i}\left(\gamma \right)$ be the γ-graph of subtree $T_i$ using only those γ-sets of $D_i$ that do not contain $x_i$. Then

$$T\left(\gamma \right)=T_1\left(\gamma \right)\square T_2\left(\gamma \right)\square \cdots \square T_k\left(\gamma \right)-(T_1^{x_1}\left(\gamma \right)\square T_2^{x_2}\left(\gamma \right)\square \cdots \square T_k^{x_k}\left(\gamma \right)).$$

Theorem 2.

[4] The γ-graph $T\left(\gamma \right)$ of every tree T is a connected graph.

Theorem 3.

[4] For any tree T, $T\left(\gamma \right)$ is $C_n$-free, for any odd $n\ge 3$. [That is, $T\left(\gamma \right)$ is bipartite.]

The main objective of this paper is the investigation of open question 4. In Section 2, we develop a method for constructing the $\gamma$-graph of a tree. In Section 3, we characterize those trees which are $\gamma$-graphs of trees. Finally, in Section 4, we state some further results for graphs which are $\gamma$-graphs of trees.

The following observations are used, frequently without reference, throughout the paper.

Observation 1.

If $D_1$ and $D_2=(D_1-\left\{u\right\})\cup \left\{v\right\}$ with $u\sim v$ are two distinct γ-sets of a tree, then $pn(D_1,u)=pn(D_2,v)\subseteq \{u,v\}$.

Observation 2.

If $u\in D$ is such that $pn(D,u)=\left\{u\right\}$, then for each $v\in N\left(u\right)$, we have that D is adjacent to $D_v=(D-\left\{u\right\})\cup \left\{v\right\}$ .

Observation 3.

If $D_1$, $D_2=(D_1-\left\{u\right\})\cup \left\{v\right\}$ and $D_3=(D_1-\left\{u\right\})\cup \left\{w\right\}$ with $v,w\in N\left(u\right)$ are three distinct $gamma$-sets of a tree, then $pn(D_1,u)=pn(D_2,v)=pn(D_3,w)=\left\{u\right\}$.

Note that Observations 1 and 3 do not hold for general graphs.

2. Computing $\gamma$-Graphs of Trees

While Fricke et al. [4] developed a method to determine the $\gamma$-graphs of trees that contain a vertex not appearing in any $\gamma$-set (Theorem 1), there are trees for which every vertex appears in some $\gamma$-set. We present a general algorithm to determine the $\gamma$-graph of a tree. We first state the following results of Edwards, MacGillivray, and Nasserasr [3] which will aid in verifying the algorithm. If D is a $\gamma$-set of a rooted tree $(T,c)$, then the depth of D, denoted $d{p}_T\left(D\right)$ (referred to as the height of D in [3]), is ${\sum }_{x\in D}d(x,c)$. Define D to be a higher$\gamma$-set than F if $d{p}_T\left(D\right)<d{p}_T\left(F\right)$ and D to be a highest γ-set if $d{p}_T\left(D\right)\le d{p}_T\left(F\right)$ for all $\gamma$-sets F of T. That is the minimum depth is equal to the greatest height.

Lemma 1.

[3] A γ-set D is a highest γ-set of a tree T rooted at a vertex c if and only if every $x\in D-\left\{c\right\}$ has a child $y\in pn(x,D)$.

Theorem 4.

[3] Let T be a tree rooted at a vertex c. Then T has a unique highest γ-set.

The algorithm DOMSET, developed by Cockayne, Goodman, and Hedetniemi [1] finds a minimum dominating set of a tree in linear time. We demonstrate that with a slight modification to the algorithm not affecting the run time, i.e., we exclude the root from being an eligible end vertex, the algorithm finds the highest minimum dominating set of a rooted tree.

Theorem 5.

Let T be a tree rooted at a vertex c. The output, S, of HIGHEST$(T,c)$ (see Algorithm 1) is the highest γ-set of T.

Algorithm 1 Let T be a tree rooted at a vertex c. We construct the highest $\gamma$-set S of $(T,c)$ as follows:

1: procedureHIGHEST($T,c$) 2:     Set $S\leftarrow \varnothing$; $G\leftarrow T$; label each vertex of T as bound. 3:     while G has an endvertex $v\ne c$ adjacent to a vertex u do 4:         if v is free then 5:            $G\leftarrow G-v$. 6:         else if v is bound then 7:            Relabel u as required; 8:            $G\leftarrow G-v$. 9:         else if v is required then 10:            $S\leftarrow S\cup \left\{v\right\}$; 11:            If u is bound then relabel u as free; 12:            $G\leftarrow G-v$. 13:         end if 14:     end while 15:     if c is not free then 16:         $S\leftarrow S\cup \left\{c\right\}$. 17:     end if 18: end procedure

Proof. 

Let D be the $\gamma$-set output by HIGHEST$(T,c)$. By Lemma 1, D is a highest $\gamma$-set of T if and only if every $x\in D-\left\{c\right\}$ has a child $y\in pn(x,D)$. Suppose there exists an $x\in D-\left\{c\right\}$ such that x has no child in $pn(x,D)$. Let y be a child of x. Either $y\in S$ or some child of y was in S. In the first case, y was relabelled required when it was processed by HIGHEST$(T,c)$ and in the latter case y was labelled required or free, when it was processed by HIGHEST$(T,c)$. In either case y was not labelled bound. But then, as y was arbitrary, x could not have been labelled as required before being processed by HIGHEST$(T,c)$, and so $x\notin S$, contradicting our assumption. Hence, together with Theorem 4, S is the highest $\gamma$-set of T. □

We now present the following algorithm for determining the $\gamma$-graph of a tree. For each vertex v in T, let $i\left(v\right)$ be its index in a breadth-first traversal of T. We note that any such algorithm must be exponential as the number of gamma sets of a tree is potentially exponential. Recently, Rote [6] provided a family of trees, referred to as the star of snowflakes, with $13k+1$ vertices and at least ${95}^k$ minimum dominating sets, i.e., trees whose number of $\gamma$-sets is on the order of $1.{4194}^n$, establishing a lower bound on the maximum number of minimum dominating sets.

The remainder of this section is devoted to verifying the correctness of GAMMATREE($T,c,S$). The index of a $\gamma$-set D, denoted here $i\left(D\right)$, is defined on line 16 of Algorithm 2. We first prove the following lemma regarding the value of the index of a $\gamma$-set.

Algorithm 2 Let T be a tree rooted at a vertex c and let S be the highest $\gamma$-set of T. For each vertex v in T, let $i\left(v\right)$ be its index in a breadth-first traversal of T. We construct the $\gamma$-graph of T, $T\left(\gamma \right)=(V,E)$, as follows:

1: procedureGAMMATREE($T,c,S$) 2:     $V\leftarrow \left\{S\right\}$; $E\leftarrow \varnothing$. 3:     $\mathrm{parents}\left(S\right)\leftarrow \varnothing$; $\mathrm{children}\left(S\right)\leftarrow \varnothing$; $i\left(S\right)\leftarrow 0$. 4:     for all $D\in V$ do 5:         for all $v\in D$ do 6:            if $pn(v,D)=\left\{v\right\}$ then 7:                $\mathrm{Swap}\leftarrow \{x:x\in N(v),i(x)>i(D\left)\right\}$. 8:            else if $pn(v,D)-\left\{v\right\}=\left\{x\right\}i\left(x\right)>i\left(D\right)$ then 9:                $\mathrm{Swap}\leftarrow \left\{x\right\}$. 10:            else 11:                $\mathrm{Swap}\leftarrow \varnothing$. 12:            end if 13:            for all $x\in \mathrm{Swap}$ do 14:                $D^{\prime }\leftarrow D-\left\{v\right\}\cup \left\{x\right\}$. 15:                $V\leftarrow V\cup \left\{D^{\prime }\right\}$; $E\leftarrow E\cup \left\{(D,D^{\prime })\right\}$. 16:                $\mathrm{parents}\left(D^{\prime }\right)\leftarrow \left\{(D,x)\right\}$; $\mathrm{children}\left(D^{\prime }\right)\leftarrow \varnothing$; $i\left(D^{\prime }\right)\leftarrow i\left(x\right)$. 17:                $\mathrm{children}\left(D\right)\leftarrow \mathrm{children}\left(D\right)\cup \left\{(D^{\prime },x)\right\}$. 18:                for all $(A,a)\in \mathrm{parents}\left(D\right)$ do 19:                    for all $(B,b)\in \mathrm{children}\left(A\right)$ do 20:                        if $b=x$ then 21:                           $E\leftarrow E\cup \left\{(D^{\prime },B)\right\}$. 22:                           $\mathrm{children}\left(B\right)\leftarrow \mathrm{children}\left(B\right)\cup \left\{(D^{\prime },a)\right\}$. 23:                           $\mathrm{parents}\left(D^{\prime }\right)\leftarrow \mathrm{parents}\left(D^{\prime }\right)\cup \left\{(B,a)\right\}$. 24:                        end if 25:                    end for 26:                end for 27:            end for 28:         end for 29:     end for 30: end procedure

Lemma 2.

Let T be a tree rooted at a vertex c and let S be the highest γ-set of T. For every γ-set $D\ne S$ found by GAMMATREE($T,c,S$),

$$i\left(D\right)=\underset{v\in D-S}{max}i\left(v\right).$$

Proof. 

Suppose $D^{\prime }$ is the first $\gamma$-set of T found by GAMMATREE($T,c,S$) such that $i\left(D^{\prime }\right)$ is not the largest index of the vertices of $D^{\prime }$ not appearing in S. By definition of $i\left(D^{\prime }\right)$, there exists a $\gamma$-set D and vertices $v,x$ such that $i\left(D^{\prime }\right)=i\left(x\right)$, $D^{\prime }=(D-\left\{v\right\})\cup \left\{x\right\}$ and $i\left(x\right)>i\left(D\right)$.

Suppose first that y is a vertex in $D^{\prime }-S$ such that $i\left(y\right)>i\left(D^{\prime }\right)$. By choice of $D^{\prime }$, we have that $i\left(D\right)={max}_{u\in D-S}i\left(u\right)$ and since $y\in D$, $i\left(D\right)\ge i\left(y\right)$. Hence, $i\left(D^{\prime }\right)=i\left(x\right)>i\left(D\right)\ge i\left(y\right)>i\left(D^{\prime }\right)$, which is a contradiction. Therefore, $i\left(y\right)\le i\left(x\right)$ for all $y\in D^{\prime }-S$ and if $x\in D^{\prime }-S$ so we assume $x\in D^{\prime }\cap S$.

Hence any vertex in $D^{\prime }$ with an index at least $i\left(x\right)$ must also be in S. In particular, x, and every descendant of x in $D^{\prime }$ must also be in S. By Lemma 1, x, and every descendant of x in S has a child S-private neighbour which is also a child $D^{\prime }$-private neighbour. Let w be a child S-private neighbour of x which is also a child $D^{\prime }$-private neighbour of x. Clearly $w\notin S$. As D is dominating and $D=(D^{\prime }-\left\{x\right\})\cup \left\{v\right\}$, it must be the case that $v=w$. Hence $i\left(D\right)={max}_{u\in D-S}\ge i\left(w\right)>i\left(x\right)$, which is a contradiction as $i\left(x\right)>i\left(D\right)$. The result follows. □

Theorem 6.

Let T be a tree rooted at a vertex c and let S be the highest γ-set of T. Every γ-set $D\ne S$ of T is obtained by GAMMATREE($T,c,S$).

Proof. 

Assume there is a $\gamma$-set of T which is not obtained by GAMMATREE($T,c,S)$. For a $\gamma$-set $D=\{v_1,v_2,\dots ,v_{\gamma \left(T\right)}\}$ of T, we define $I\left(D\right)=\{i\left(v_1\right),i\left(v_2\right),\dots ,i\left(v_{\gamma \left(T\right)}\right)\}$, where $i\left(v_1\right)<i\left(v_2\right)<\cdots <i\left(v_{\gamma \left(T\right)}\right)$. Let $D^{\prime }$ be the $\gamma$-set not obtained by GAMMATREE($T,c,S$) for which $I\left(D^{\prime }\right)$ is lexicographically smallest. Let x be so that $i\left(x\right)=i\left(D^{\prime }\right)$. Then every descendant of x in $D^{\prime }$ has a higher index and hence is also in S. It follows from Lemma 1, each descendant of x in $D^{\prime }$ has a child $D^{\prime }$-private neighbour. If x also has a child $D^{\prime }$-private neighbour, then every higher $\gamma$-set of T must contain x, contradicting that $x\notin S$. Hence, no child of x is a $D^{\prime }$-private neighbour. Therefore, if v is the parent of x, then the set $D=D^{\prime }-\left\{x\right\}\cup \left\{v\right\}$ is a $\gamma$-set of T. Since $I\left(D\right)$ is lexicographically smaller than $I\left(D^{\prime }\right)$, D is found by GAMMATREE($T,c,S$). Clearly each vertex in $D-S\subseteq (D^{\prime }-S)\cup \left\{v\right\}$ has a smaller index than x, so $i\left(x\right)>i\left(D\right)$. Further, as D and $D^{\prime }$ are both $\gamma$-sets of T, $pn(v,D)\subseteq \{v,x\}$, so for $v\in D$, $x\in \mathrm{Swap}$. Hence, $D^{\prime }$ is found by GAMMATREE($T,c,S$), which is a contradiction proving the theorem. □

Finally, we will show GAMMATREE($T,c,S$) obtains every edge of $T\left(\gamma \right)$. We first demonstrate that the $\gamma$-sets are obtained by GAMMATREE$(T,c,S)$ in order of depth.

Lemma 3.

The algorithm GAMMATREE$(T,c,S)$ can be implemented so that the γ-sets of T are obtained in order of depth.

Proof. 

Let D be a $\gamma$-set obtained by GAMMATREE($T,c,S)$. As GAMMATREE($T,c,S)$ runs, store the dominating sets of T (these are the elements of V) in a queue, so that first one discovered by GAMMATREE($T,c,S)$ is the first one processed by GAMMATREE($T,c,S)$. It suffices to prove that every $\gamma$-set $D^{\prime }$ found from D (i.e., at line 14) is such that $d{p}_T\left(D^{\prime }\right)=d{p}_T\left(D\right)+1$. We observe that $D^{\prime }=(D-\left\{v\right\})\cup \left\{x\right\}$ for adjacent vertices v and x. If $D=S$, then every $z\in D-\left\{c\right\}$ has a child $y\in pn(z,D)$, so x is a child of v and $d{p}_T\left(D^{\prime }\right)=d{p}_T\left(D\right)+1$ as desired. Now suppose $D\ne S$. If $i\left(v\right)>i\left(D\right)$, then by Lemma 2, $v\in S$ and every descendant of v which is in D is also in S. It follows that v has a child $y\in pn(v,D)$, so x must be a child of v, and $d{p}_T\left(D^{\prime }\right)=d{p}_T\left(D\right)+1$ as desired. Otherwise, $i\left(v\right)\le i\left(D\right)$ and $i\left(x\right)>i\left(D\right)$. Then it is clear that x is a child of v, and the result again follows. □

Theorem 7.

Let T be a tree rooted at a vertex c and let S be the highest γ-set of T. The algorithm GAMMATREE$(T,c,S)$ can be implemented so that each edge in $T\left(\gamma \right)$ is obtained by GAMMATREE($T,c,S$).

Proof. 

Implement algorithm GAMMATREE$(T,c,S)$ as required in Lemma 3 and suppose not all edges of $\gamma \left(T\right)$ are obtained. Let $D_1$ be the first $\gamma$-set found by GAMMATREE($T,c,S$) such that there exists a $\gamma$-set $D_2$, found before $D_1$, where $D_2=(D_1-\left\{z\right\})\cup \left\{y\right\}$, $yz\in E\left(T\right)$, but edge $D_1{D}_2$ is not obtained by GAMMATREE($T,c,S$). By Lemma 3, $d{p}_T\left(D_2\right)=d{p}_T\left(D_1\right)-1$. As $D_1$ and $D_2$ are both $\gamma$-sets of T, we have $pn(z,D_1)=pn(y,D_2)\subseteq \{y,z\}$. Suppose $i\left(x\right)=i\left(D_1\right)$. Then by Lemma 3, $D_1$ was found while processing a set $D_3=(D_1-\left\{x\right\})\cup \left\{w\right\}$, where w is the parent of x in T. Clearly, neither $D_2$ nor $D_3$ is S. Hence, there exists a $\gamma$-set $D_4$ such that $D_4=(D_3-\left\{z\right\})\cup \left\{y\right\}=(D_2-\left\{x\right\})\cup \left\{w\right\}$. Moreover, since w is the parent of x, we have

$$d{p}_T\left(D_4\right)+1=d{p}_T\left(D_3\right)=d{p}_T\left(D_2\right)=d{p}_T\left(D_1\right)-1,$$

so $D_4$ is found before $D_2$ and $D_3$ by Lemma 3. Hence, $D_2{D}_4$ and $D_3{D}_4$ were both obtained by GAMMATREE($T,c,S$). In particular, $(D_4,z)\in \mathrm{parents}\left(D_3\right)$ and $(D_2,x)\in \mathrm{children}\left(D_4\right)$. Thus, we obtain the edge $D_1{D}_2$ when processing $D_3$, which is the contradiction proving the theorem. □

The correctness of the algorithm immediately follows.

Corollary 1.

Let T be a tree rooted at a vertex c and let S be the highest γ-set of T. The algorithm GAMMATREE($T,c,S$) can be implemented to produce $T\left(\gamma \right)$.

Proof. 

By Theorem 6, we obtain every vertex of $T\left(\gamma \right)$, and by Theorem 7, we obtain every edge of $T\left(\gamma \right)$. The result follows. □

3. $\gamma$-Trees of Trees

In this section, we characterize the trees which are $\gamma$-graphs of trees. We first consider properties of the $\gamma$-sets corresponding to the leaves of a $\gamma$-graph. (Recall we equate each node in $G\left(\gamma \right)$ with its corresponding $\gamma$-set of G.)

Lemma 4.

Let T be a tree with at least three vertices and let $T\left(\gamma \right)$ be the γ-graph of T. If D is a leaf in $T\left(\gamma \right)$, then exactly one vertex $v\in D$ has fewer than two D-external private neighbours. Furthermore either v has exactly one D-external private neighbours or v is both a leaf in T and a D-self private neighbour.

Proof. 

Note that if every vertex of dominating set D in a tree has at least two D-external private neighbours, D has no neighbours in $T\left(\gamma \right)$. If a vertex x in T has exactly one external private neighbour y in D, then $(D-\{x\left\}\right)\cup \left\{y\right\}$ is a $\gamma$-set of T adjacent to D. If a vertex z in T has no external private neighbours in D, then z must be a self private neighbour in D and for every $w\in N\left(z\right)$, $(D-\{z\left\}\right)\cup \left\{w\right\}$ is a $\gamma$-set of T adjacent to D. As D is adjacent to exactly one $\gamma$-set, the result follows. □

Next, we prove a fundamental result on the number of private neighbours of a vertex in adjacent $\gamma$-sets of a tree.

Lemma 5.

Let D and F be γ-sets of a tree T which are adjacent in $T\left(\gamma \right)$ and let $x\in D\cap F$. Then $\left|pn\right(x,D)\setminus pn(x,F\left)\right|\le 1$ and $\left|pn\right(x,F)\setminus pn(x,D\left)\right|\le 1$.

Proof. 

Suppose $F=(D-\{y\left\}\right)\cup \left\{z\right\}$ for adjacent vertices y and z in T. Let $x\in D\cap F$. Suppose the result is false and assume without loss of generality that $\left|pn\right(x,D)\setminus pn(x,F\left)\right|\ge 2$. If x is a D-self private neighbour, but not an F-self private neighbour, then $z\sim x$ and z is adjacent to a D-external private neighbour of x, say w. Then of $xwz$ is a 3-cycle in T, which contradicts that T is a tree. Otherwise, x has at least two D-external private neighbours $v,w$ that are adjacent to z, so $xvzw$ is a 4-cycle in T, which contradicts that T is a tree. The result follows. □

We now consider the $\gamma$-sets of leaves adjacent to the same stem.

Lemma 6.

Let T be a tree and let $T\left(\gamma \right)$ be the γ-graph of T. If S is a stem in $T\left(\gamma \right)$ with degree at least three and $L_1,L_2,\dots ,L_k$ are the leaves of S, then there exists vertices $x\in S$ and $y_1,y_2,\dots ,y_k\in V\left(T\right)-S$ so that $x\sim y_i$ and $L_i=(S-\left\{x\right\})\cup \left\{y_i\right\}$ for $i=1,2,\dots k$.

Proof. 

If $k=1$, the statement is trivial, so assume $k\ge 2$. As S is adjacent to $L_i$ in $T\left(\gamma \right)$, for each i there exists vertices $x_i$ and $y_i$ so that $L_i=(S-\left\{x_i\right\})\cup \left\{y_i\right\}$ and $x_i\sim y_i$. Let $X=\{x_i:i=1,2,\dots ,k\}\subseteq S$. Suppose $\left|X\right|\ge 2$. By Lemma 4, $y_i$ is the only vertex in $L_i$ with fewer than two $L_i$-external private neighbours. In particular, if $x_i\ne x_j$, then $x_i$ has at least two $L_j$-external private neighbours. It now follows from Lemma 5, that each $x_i$ has an S-external private neighbour.

If $x_i\ne x_j$, then $S-\{x_i,x_j\}\cup \{y_i,y_j\}$ is not a $\gamma$-set of T as $L_i$ and $L_j$ are leaves of $T\left(\gamma \right)$. Hence there exists a vertex $z_{ij}$ which is not dominated by $S-\{x_i,x_j\}\cup \{y_i,y_j\}$. It must be the case that both $x_i$ and $x_j$ are neighbours of $z_{ij}$. If $\left|X\right|\ge 3$, then each such $z_{ij}$ must be identical or T is not a tree, but then $S-\{x_i,x_j\}\cup \{y_i,y_j\}$ is dominating, a contradiction. Hence we assume $\left|X\right|=2$, say $X=\{x_1,x_2\}$. 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, $\left|X\right|=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 γ-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-\left\{x\right\})\cup \left\{y_i\right\}$ and $M_i=(R-\left\{w\right\})\cup \left\{z_i\right\}$ where $y_1,y_2\in N\left(x\right)$ and $z_1,z_2\in N\left(w\right)$. Further there exists $u\in S$ so that $R=(S-\{u\left\}\right)\cup \left\{v\right\}$ 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\ne u$ and by Lemma 5, x has at most one R-external private neighbour. Hence, there exists a vertex $y^{\prime }\in N\left(x\right)$ such that $Q:=(R-\left\{x\right\})\cup \left\{y^{\prime }\right\}$ is a $\gamma$-set of T. As $x\ne u$ and R has only three neighbours, it follows that $Q\in \{M_1,M_2\}$ and therefore $x=w$. By Observation 2, $N\left(x\right)=\{y_1,y_2\}$ and $N\left(w\right)=\{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-\left\{u\right\}\cup \left\{v\right\}$. Thus, $L_1$ and $M_1$ are neighbours in H, which is a contradiction.

Hence it must be that $x\notin R$. By symmetry, $w\notin 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 γ-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 γ-set of T containing x.

Proof. 

Consider $T^{\prime }$ a component of $T-N\left[x\right]$. Then $D\cap V\left(T^{\prime }\right)$ is clearly a dominating set of $T^{\prime }$. If $D\cap V\left(T^{\prime }\right)$ is not also a $\gamma$-set of $T^{\prime }$, then D is not minimal. Hence $D\cap V\left(T^{\prime }\right)$ is a $\gamma$-set of $T^{\prime }$ and since each vertex of $D-\left\{x\right\}$ has at least two D-external private neighbours, $D\cap V\left(T^{\prime }\right)$ has no neighbours in $T^{\prime }\left(\gamma \right)$. It follows from Theorem 2 that $D\cap V\left(T^{\prime }\right)$ is the only $\gamma$-set of $T^{\prime }$. As T is a tree, the vertices in $N\left(x\right)$ are adjacent to at most one vertex in $T^{\prime }$. Recall each vertex of $D\cap V\left(T^{\prime }\right)$ has at least two D-external private neighbours. Let E be a $\gamma$-set of T containing x. Then $E\cap V\left(T^{\prime }\right)$ must contain at least $|D\cap V(T^{\prime }\left)\right|$ vertices. Since $T^{\prime }$ was arbitrary, $\left|D\right|=\left|E\right|=\gamma \left(T\right)$ and $|D\cap V\left(T^{\prime }\right)|=|E\cap V\left(T^{\prime }\right)|$, the set E has at most one vertex in $N\left[x\right]$, namely x. For any component, $T^{\prime }$ of $T-N\left[x\right]$, $D\cap V\left(T^{\prime }\right)$ is the unique $\gamma$-set of $T^{\prime }$. Therefore D is the unique $\gamma$-set of T containing x. □

Theorem 8.

If G is a γ-graph of a tree T and L is a leaf of G, then $G-L$ is a γ-graph of some tree $T^{\prime }$.

Proof. 

By Lemma 4, exactly one vertex x in L has fewer than two L-external private neighbours. Moreover, either x has exactly one L-external private neighbour or x is a leaf in T and an L-self private neighbour. By Lemma 8, L is the unique $\gamma$-set of T containing x.

If x is a leaf of T and is an L-self private neighbour, then $T^{\prime }$ is formed by adding a leaf to the stem of x. Suppose on the other hand, x has exactly one external private neighbour y. If x is a self private neighbour, then $T^{\prime }$ is formed by rooting T at y, deleting the descendants of x, and adding a leaf to y. Otherwise, $T^{\prime }$ is formed by rooting T at y, and deleting x and its descendants. □

Corollary 2.

If G is a tree and a γ-graph of a tree T, then every subtree of G is a γ-graph of some tree.

Corollary 3.

If G is a tree and a γ-graph of a tree T, then $\mathbf{H}$ is not a subtree of G.

Proof. 

The result immediately follows from Lemma 7 and Corollary 2. □

From the previous corollary, we know that if a tree is a $\gamma$-graph of a tree, then the vertices of degree at least three are not adjacent. We now wish to show all trees without adjacent vertices of degree at least three are the $\gamma$-graph of a tree. The proof is constructive. We establish first some building blocks.

Theorem 9.

Let $Y_n$ be the graph obtained by taking n copies of $K_{1,3}$ and joining a leaf of each copy to a common vertex (see Figure 2 for an example). Then $Y_n\left(\gamma \right)\cong K_{1,n}$, and in every γ-set which is a leaf of $K_{1,n}$, every vertex has an external private neighbour.

Proof. 

Since every stem of $Y_n$ is adjacent to two leaves, every $\gamma$-set of $Y_n$ must contain every stem. Only the common centre vertex is left to be dominated, so we can form a $\gamma$-set by adding this vertex or any of its neighbours. Further, the only edges are between the $\gamma$-set containing the common centre vertex and each of the other $\gamma$-sets. Finally, in each of these other $\gamma$-sets, every stem has at least two external private neighbours, its leaves, and the additional vertex has the common centre vertex as its private neighbour. The result follows. □

We now provide a tool for combining these building blocks.

Lemma 9.

Suppose for $i=1,2$, $G_i$ is a γ-graph of tree $T_i$, $X_i$ is a leaf of $G_i$ and every vertex in the dominating set $X_i$ has at least one $X_i$-external private neighbour. By Lemma 4, in each $X_i$ there is exactly one vertex $v_i\in V\left(T_i\right)$ with fewer than two $X_i$-external private neighbours. Then G, the graph formed by identifying $X_1$ and $X_2$ is the γ-graph of a tree $T:\cong T_1{\oplus }_{v_2}^{v_1}{T}_2$, the tree formed by linking $T_1$ and $T_2$ by creating a new vertex v adjacent to $v_1$ and $v_2$.

Furthermore let $Y\in V\left(G_1\right)$ be a dominating set of $T_1$ and $Y^{\prime }\in V\left(G\right)$ be the corresponding dominating set of T. If every vertex of Y has a Y-external private neighbour, then every vertex in $Y^{\prime }$ has a $Y^{\prime }$-external private neighbour.

Proof. 

By Lemma 4, exactly one vertex $v_i$ in $X_i$ has fewer than two external private neighbours. It follows that $v_i$ has exactly one external private neighbour. Form T from $T_1$ and $T_2$ by adding a new vertex v with $N\left(v\right)=\{v_1,v_2\}$. We now show that $T\left(\gamma \right)\cong G$.

It is clear that $\gamma \left(T\right)\le \gamma \left(T_1\right)+\gamma \left(T_2\right)$. Suppose some $\gamma$-set D of T contains v. Then without loss of generality, $\gamma (T_1-\left\{v_1\right\})<\gamma \left(T_1\right)$. Let $D^{\prime }$ be a $\gamma$-set of $T-\left\{v_1\right\}$. Then no neighbour of $v_1$ is in $D^{\prime }$. Hence $D^{\prime }\cup \left\{v_1\right\}$ is a $\gamma$-set of $T_1$ and $v_1$ has no external private neighbours. Then, by Lemma 8, $D^{\prime }\cup \left\{v_1\right\}$ is the unique $\gamma$-set of $T_1$ containing $v_1$, so $D^{\prime }\cup \left\{v_1\right\}=X_1$. But this contradicts the presupposition that every vertex in $X_1$ has an $X_1$-external private neighbour. Hence no $\gamma$-set of T contains v, $\gamma \left(T\right)=\gamma \left(T_1\right)+\gamma \left(T_2\right)$ and every $\gamma$-set of T is the union of a $\gamma$-set of $T_1$ and a $\gamma$-set of $T_2$.

Every $\gamma$-set of T must contain $v_1$ or $v_2$ for v to be dominated. Let $X=X_1\cup X_2$. It is clear that X is the unique $\gamma$-set containing both $v_1$ and $v_2$. Since every other vertex in X has least two external private neighbours, and $v_1$ and $v_2$ have exactly one external private neighbour, X is adjacent to two $\gamma$-sets. Let D be a dominating set of T other than X. If $v_2\in D$ and by Lemma 8, $D\cap T_2\cong X_2$ and every vertex in $D\cap T_2$ has at least two D-external private neighbours. Therefore the subgraph of the $\gamma$-sets of T containing $v_2$ in $T\left(\gamma \right)$ is $G_1$ and similarly the subgraph of the $\gamma$-sets of T containing $v_1$ in $T\left(\gamma \right)$ is $G_2$. Hence, the $\gamma$-graph of T is G as required. The final statement follows directly from the above construction. □

We can now prove the main result.

Theorem 10.

If G is a tree, then G is a γ-graph of some tree if and only if H is not a subtree of G.

Proof. 

Necessity follows by Corollary 3; it remains to show sufficiency. The result trivially holds for $K_1$ as $K_1\left(\gamma \right)\cong K_1$; so suppose G has at least two vertices. We proceed by induction on k, the number of degree two vertices of G. If $k=0$, then $G\cong K_{1,n-1}$, and by Theorem 9, $K_{1,n-1}$ is the $\gamma$-graph of $Y_{n-1}$, and in every $\gamma$-set which is a leaf of $K_{1,n-1}$, every vertex has an external private neighbour.

Assume $k>0$ and that every tree F not containing H as a subtree with fewer than k degree two vertices is the $\gamma$-graph of some tree and in every $\gamma$-set which is a leaf of F, every vertex has an F-external private neighbour. Let x be a degree two (cut-)vertex in G, and let $G_1$ and $G_2$ be the two components of $G-\left\{x\right\}$. As $G_1\cup \left\{x\right\}$ and $G_2\cup \left\{x\right\}$ each have fewer than k degree two vertices, then by the induction hypothesis, each is the $\gamma$-graph of a tree (say $T_1$ and $T_2$ respectively) and in every $\gamma$-set which is a leaf of $T_1$ and $T_2$ repsectively, every vertex has an external private neighbour. By Lemma 9, there are vertices $v_1\in V\left(T_1\right)$ and $v_2\in V\left(T_2\right)$ so that the $\gamma$-graph of $T_1{\oplus }_{v_2}^{v_1}{T}_2$ is G and by construction, in every $\gamma$-set which is a leaf of G, every vertex has an external private neighbour. The result follows. □

4. Properties of $\gamma$-Graphs of Trees

In this section, we investigate general properties of $\gamma$-graphs of trees. We begin with a result classifying the edges in $\gamma$-graphs of trees, highlighting the importance of cut edges and 4-cycles in these graphs.

Lemma 10.

Let T be a tree and let $T\left(\gamma \right)$ be the γ-graph of T. Every edge of $T\left(\gamma \right)$ is a cut-edge or is contained in a 4-cycle.

Proof. 

Let e be an edge which is not a cut-edge of $T\left(\gamma \right)$. Then e is contained in a cycle. But cycles in Algorithm 2 are only created at line 21, which always creates a 4-cycle. The result follows. □

We now show that a cut-edge, not incident with a leaf allows you to decompose a $\gamma$-graph of a tree into two smaller graphs, both of which are also $\gamma$-graphs of trees.

Lemma 11.

Let G be a γ-graph of a tree T with a cut-edge e, and let $G_1$ and $G_2$ be the components of $G\setminus e$. Then $G_1+e$ and $G_2+e$ are each γ-graphs of trees.

Proof. 

Let $e=AB$ with $A\in V\left(G_1\right)$ and $B\in V\left(G_2\right)$ and assume $A=(B-\{y\left\}\right)\cup \left\{z\right\}$. Let $\left\{z\right\}\cup \left\{z_i\right\}$ be the set of vertices that can be swapped from B. Form $T^{\prime }$ by adding a leaf to each $z_i$. Since e is a cut-edge, $z_i$ cannot be swapped in A, and hence each $z_i$ has exactly one external private neighbour in B. But B is also a $\gamma$-set of $T^{\prime }$, and each $z_i$ has two external private neighbours. Moreover, each $\gamma$-set in $G_1$ is also a $\gamma$-set of $T^{\prime }$, so it follows that $G_1+e$ is the $\gamma$-graph of $T^{\prime }$. By symmetry, $G_2+e$ is also the $\gamma$-graph of a tree. □

Setting $G=H$ (see Figure 1) and e the edge joining the two stems of H, shows the converse of Lemma 11 does not necessarily hold. That is both $G_1+e=K_{1,3}$ and $G_2+e=K_{1,3}$ are each $\gamma$-graphs of trees, but $G=H$ is not a $\gamma$-graph of any tree. Lemma 11 does provide a tool for showing a graph with a cut-edge not incident to a leaf is not the $\gamma$-graph of any tree T. For example, consider the graph Z shown in Figure 3. Let $Z_1$ and $Z_2$ be the components of Z obtained by deleting the edge e, where $Z_2$ is a tree. Then $Z_2+e$ is a tree with adjacent vertices of degree at least 3 and thus by Theorem 10, $Z_2+e$ is not the $\gamma$-graph of any tree T. It now follows from Lemma 11 that Z is not the $\gamma$-graph of any tree T.

The remainder of the paper will focus on $\gamma$-graphs of trees where every edge is in a 4-cycle or incident with a leaf. We first present the following useful result due to Edwards, MacGillivray, and Nasserasr [3], which will be applied throughout.

Lemma 12.

[3] For a γ-set D of a tree T and a vertex $z\notin D$, there is at most one vertex $v\in D$ such that $(D-\{v\left\}\right)\cup \left\{z\right\}$ is also a γ-set of T.

We now demonstrate a key property of the $\gamma$-sets which when equated to their vertices form a 4-cycle of $T(\gamma$) that we will make extensive use of in our next set of results.

Proposition 2.

If G is a γ-graph of a tree T and $WXYZ$ is a 4-cycle of G, then for some distinct $a,b\in W$ and distinct $c,d\notin W$ with $a\sim c$ and $b\sim d$, $X=(W-\{a\left\}\right)\cup \left\{c\right\}$, $Z=(W-\{b\left\}\right)\cup \left\{d\right\}$ and $Y=(W-\{a,b\left\}\right)\cup \{c,d\}=(Z-\{a\left\}\right)\cup \left\{c\right\}=(X-\{b\left\}\right)\cup \left\{d\right\}$.

Proof. 

For some $p,r\in W$ and $q,s\notin W$ with $p\sim q$ and $r\sim s$ we have $X=(W-\{p\left\}\right)\cup \left\{q\right\}$ and $Z=(W-\{r\left\}\right)\cup \left\{s\right\}$. It follows from Lemma 12 that $q\ne s$. If $q,s\notin Y$, then as $Y\ne W$, for some vertex $t\notin X\cup Z$, with $q,s\in N\left(t\right)$, $Y=(X-\{q\left\}\right)\cup \left\{t\right\}=(Z-\{s\left\}\right)\cup \left\{t\right\}$ and $p=r$ with $p\notin Y$. But then $pqts$ is a 4-cycle in T, which contradicts that T is a tree. Hence either $q\in Y$ or $s\in Y$. Suppose without loss of generality $q\in Y$. In the case that $s\notin Y$, then $Y=(Z-\{s\left\}\right)\cup \left\{q\right\}$ and therefore $(X-\{r\left\}\right)\cup \left\{p\right\}$. This implies s is adjacent to q in T and r is adjacent to p in T (with $p\ne r$). But then $pqsr$ is a 4-cycle in T, contradicting that T is a tree. Hence, $q,s\in Y$. If $p=r$, then there exists a vertex $u\in W$ so that $Y=(X-\{u\left\}\right)\cup \left\{s\right\}=(Z-\{u\left\}\right)\cup \left\{q\right\}$ and hence both s and q are adjacent to u in T. It follows that $suqp(=r)$ is a cycle in T, showing that p and r are distinct. Thus $Y=(W-\{p,r\left\}\right)\cup \{q,s\}$, as required. □

4.1. 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. Sabidussi [7] and Vizing [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\left(\gamma \right)$ , where $D_1$ and $D_2$ are $\gamma$-sets of T. Define $sw\left(e\right)=\{x,y\}$, the unique vertices x and y so that $D_2=(D_1-\left\{x\right\})\cup \left\{y\right\}$.

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\left(\gamma \right)$, there exists vertices $x,y\in V\left(T\right)$ so that $D_2=(D_1-\left\{x\right\})\cup \left\{y\right\}$. Hence $sw\left(e_1\right)=\{x,y\}$. By Proposition 2, it is also the case that $sw\left(e_2\right)=\{x,y\}$ and if $e^{\prime }$ is incident with $e_1$, then $x\notin sw\left(e^{\prime }\right)$ and $y\notin sw\left(e^{\prime }\right)$. Repeated applications of Proposition 2 shows that each of $sw\left(e_3\right)=sw\left(e_4\right)=sw\left(e_5\right)=\{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\notin sw\left(e^{\prime }\right)$ and $y\notin sw\left(e^{\prime }\right)$. Similarly there are vertices $a,b\in V\left(T\right)$ so that $sw\left(f_1\right)=sw\left(f_2\right)=sw\left(f_3\right)=sw\left(f_4\right)=\{a,b\}$ and that $a\notin sw\left(e^{\prime \prime }\right)$ and $b\notin sw\left(e^{\prime \prime }\right)$ 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\}=\varnothing$. More generally let $E_1$ be the set of edges of $C_4\square P_5$ associated with edges of $C_4$ and let $E_2$ be the set of 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\left(e^{\prime }\right)\right)\bigcap \left(\bigcup _{e^{\prime }\in E_2}sw\left(e^{\prime }\right)\right)=\varnothing .$$

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 × symbols. Add two leaves to each vertex in $D\cap \left({\bigcup }_{e^{\prime }\in E_1}sw\left(e^{\prime }\right)\right)=\{y,z\}$ to form a tree $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\left(\gamma \right)$ is isomorphic to $P_5$.

For convenience in the following proof if $v\in sw\left(e\right)$ we will say v is swapped by e and that e swaps v.

Theorem 12.

Let G be a Cartesian product graph with $G=G_1\square G_2$, $G_i\ne K_1$. Then G is the γ-graph of a tree T if and only if each $G_i$ is the γ-graph of a tree $T_i$.

Proof. 

Suppose $G=G_1\square G_2$, $G_1,G_2\ne K_1$, is the $\gamma$-graph of a tree T. Let $e=U_1{U}_2$ be an edge of $G_1$ and let $e_1$ and $e_2$ be any two edges associated with e in G on vertices $V_1$ and $V_2$ of $G_2$ respectively. That is $e_1=(U_1,V_1)(U_2,V_1)$ and $e_2=(U_1,V_2)(U_2,V_2)$. As G is connected by Theorem 2, there is a path between $(U_1,V_1)$ and $(U_1,V_2)$ in G, and considering only the edges associated with edges in $G_2$ gives a path P between $V_1$ and $V_2$ in $G_2$. Consider the subgraph $e\square P$ of G. It follows from Proposition 2 that every edge associated with e in $e\square P$ swaps the same pair of vertices. As $e_1$ and $e_2$ were arbitrary edges associated with e, then every edge associated with e in G swaps the same pair of vertices. By symmetry, this is true of every edge in $G_1$ or $G_2$. Let $(W,X)$ be a vertex of G and for $i=1,2$, let $E_i$ be the set of edges of G associated with the edges of $G_i$. If a vertex $a\in (W,X)$ is swapped by an edge in $E_2$, it is not swapped by an edge in $E_1$ by Proposition 2. Hence, form $T_1$ by adding two leaves to any vertex in $(W,X)$ that is swapped by an edge in $E_2$. Then it follows that $T_1\left(\gamma \right)\cong G_1$. By symmetry, $G_2$ is also the $\gamma$-graph of a tree.

Conversely, suppose each $G_i$ is the $\gamma$-graph of a tree $T_i$. Let T be the graph formed by adding an edge between any stem of $T_1$ and any stem of $T_2$. It is easily verified that $T\left(\gamma \right)\cong G$. □

4.2. Incident 4-Cycles in $\gamma$-Graphs of Trees

In this subsection we give some structure to how four cycles interact locally in $\gamma$-graphs of a trees. We first demonstrate that $K_{2,3}$ cannot be a subgraph of a $\gamma$-graph of a tree. As a consequence, we observe that two 4-cycles have at most two common vertices, and moreover, if two 4-cycles have two common vertices, then the two common vertices are adjacent.

Theorem 13.

Let T be a tree and let $T\left(\gamma \right)$ be the γ-graph of T. Then $T\left(\gamma \right)$ does not contain $K_{2,3}$ as a subgraph.

Proof. 

For $i\in \{1,2,3\}$ and $j\in \{1,2\}$ let $Y_i$ and $X_j$ be vertices of $T\left(\gamma \right)$ that induce $K_{2,3}$. That is $X_j\sim Y_i$ for each possible i and j. Then for each $i\in \{1,2,3\}$ there exist vertices $a_i\in X_1$ and $b_i\notin X_1$ with $a_i\sim b_i$ and $Y_i=(X_1-\left\{a_i\right\})\cup \left\{b_i\right\}$. By Lemma 12, it must be the case that $b_1$, $b_2$ and $b_3$ are all distinct. It follows from Theorem 3 that $X_1$ and $X_2$ are at distance two in $T\left(\gamma \right)$. Therefore $|X_2\setminus X_1|\le 2$ and so for some i, $b_i\notin X_2\setminus X_1$. Assume with out loss of generality $b_3\notin X_2\setminus X_1$. As $b_3\notin X_1$ it must be the case that $b_3\notin X_2$. Then for some vertex $c\notin Y_3$ with $c\sim b_3$, $X_2=(Y_3-\left\{b_3\right\})\cup \left\{c\right\}$, and it follows that $X_2=(X_1-\left\{a_3\right\})\cup \left\{c\right\}$ and therefore $a_3\ne c$. As each $b_i$ is distinct, we can assume without loss of generality that $b_2\ne c$. Then $X_2=(Y_2-\{a_3,b_2\})\cup \{a_2,c\}$. But $d(X_2,Y_2)=1$, so $|X_2\setminus Y_2|=1$, which shows it must be the case that $a_2=a_3$. Clearly $b_2$ and $b_3$ are both adjacent to $a_3$ in T. Furthermore $X_2$ is adjacent to $Y_2$ in G and $X_2=(Y_2-\left\{b_2\right\})\cup \left\{c\right\}$ so it must be the case that $b_2$ is adjacent to c in T. By definition, $c\sim b_3$ so either $c{b}_2{a}_3{b}_3$ forms a cycle in T or $c=a_3$. Both cases lead to a contradiction. □

We have shown that two 4-cycles in $T\left(\gamma \right)$ cannot overlap in more than two vertices. On the other hand, we can also say something about the structure required in $T\left(\gamma \right)$ when two 4-cycles have only one common vertex. We first establish the following.

Proposition 3.

Let G be a γ-graph of a tree T and let $C=WXYZ$ be a 4-cycle of G. By Proposition 2 there are distinct $a,b\in W$ and distinct $c,d\notin W$ with $a\sim c$ and $b\sim d$, so that $X=(W-\{a\left\}\right)\cup \left\{c\right\}$, $Z=(W-\{b\left\}\right)\cup \left\{d\right\}$ and $Y=(W-\{a,b\left\}\right)\cup \{c,d\}$. If U and V are each adjacent to W but not part of a 4-cycle with a pair of vertices of C and $U=(W-\{e\left\}\right)\cup \left\{f\right\}$ and $V=(W-\{g\left\}\right)\cup \left\{h\right\}$, then $e=g$.

Proof. 

Suppose the opposite. It follows from Lemma 12 that c, d, f and h are all distinct. As neither U nor V is part of a 4-cycle with any two vertices of C, $(W-\{a,e\left\}\right)\cup \{c,f\}$ is not a $\gamma$-set of T. Hence, if $a\ne e$, a and e have common neighbour i which is not adjacent to any vertex in $(W-\{a,e\left\}\right)\cup \{c,f\}$. As b, $g\in (W-\{a,e\left\}\right)\cup \{c,f\}$, i is not adjacent to b or g in T. Similarly it can be seen $(W-\{b,e\left\}\right)\cup \{d,f\}$, $(W-\{a,g\left\}\right)\cup \{c,h\}$, and $(W-\{b,g\left\}\right)\cup \{d,h\}$ are not $\gamma$-sets of T. Hence, if $b\ne e$, b and e have common neighbour j not adjacent to a or g, if $a\ne g$, then a and g have common neighbour k not adjacent to b or e, and if $b\ne g$, b and g have common neighbour l not adjacent to a or e. It can be seen that $i,j,k,l$ (if they exist) are all distinct.

Suppose $a=e$. Then as a and b are distinct, $b\ne e$. Hence, b and e have common neighbour j not adjacent to $a=e$, a contradiction. Hence $a\ne e$. Similarly we can show $b\ne e$, $a\ne g$ and $b\ne g$. But then $aiejblgk$ is a cycle in T, contradicting that T is a tree. The result follows. □

Proposition 4.

Let G be a γ-graph of a tree T and let $WXYZ$ and $WVUS$ be 4-cycles of G. Then there must be a 4-cycle $WRQP$, with $R\in \{X,Z\}$ and $P\in \{S,V\}$.

Proof. 

Suppose not. Then neither S nor V is part of a 4-cycle with a pair vertices of $WXYZ$. Hence, by Proposition 2 there are distinct vertices $a,b\in W$ and $c,d\notin W$, with $a\sim c$ and $b\sim d$ so that $S=(W-\{a\left\}\right)\cup \left\{c\right\}$ and $V=(W-\{b\left\}\right)\cup \left\{d\right\}$. By Proposition 3, $a=b$, a contradiction. The result follows. □

Define two 4-cycles of G to be adjacent if they share an edge and two adjacent cycles to be neighbours. Then Proposition 4 can be reworded to say that incident 4-cycles in a $\gamma$-graph of a tree must be adjacent to each other or have a common neighbour. We conclude our treatment of vertices of 4-cycles by demonstrating that adjacent vertices of a 4-cycle cannot both have vertex neighbours that are not part of neighbouring 4-cycles.

Proposition 5.

Let G be the γ-graph of a tree and let C be an induced $C_4$ of G. Then in any two adjacent vertices of C at most one has a neighbour which is not part of a 4-cycle with a pair of vertices of C.

Proof. 

Suppose G is the $\gamma$-graph of a tree T. Let $C=WXYZ$ and suppose that W and X have neighbours U and V respectively, which are not part of a 4-cycle with any two vertices of C. Recall a vertex of the $\gamma$-graph is a $\gamma$-set. By Proposition 2, there are distinct vertices $a,b\in W$ and $c,d\notin W$ so that $a\sim c$, $b\sim d$, $X=(W-\{a\left\}\right)\cup \left\{c\right\}$, $Z=(W-\{b\left\}\right)\cup \left\{d\right\}$ and $Y=(W-\{a,b\left\}\right)\cup \{c,d\}$. There are vertices $e\in W$, $g\in X$, $f\notin W$ and $h\notin X$ so that $e\sim f$, $g\sim h$, $U=(W-\{e\left\}\right)\cup \left\{f\right\}$ and $V=(X-\{g\left\}\right)\cup \left\{h\right\}$. We note from Lemma 12 that d, f and c are all distinct and that d, h and a are all distinct. As neither U nor V is part of a 4-cycle with any two vertices of C we get:

• if $a\ne e$, then as $(W-\{a,e\left\}\right)\cup \{c,f\}$ is not a $\gamma$-set of T, a and e have a common neighbour $i\notin N\left[b\right]\cup N\left[c\right]$.
• if $b\ne e$, then as $(W-\{b,e\left\}\right)\cup \{d,f\}$ is not a $\gamma$-set of T, b and e have a common neighbour $j\notin N\left[a\right]$.
• if $b\ne g$, then as $(X-\{b,g\left\}\right)\cup \{d,h\}$ is not a $\gamma$-set of T, b and g have a common neighbour $k\notin N\left[c\right]$.
• if $c\ne g$, then as $(X-\{c,g\left\}\right)\cup \{a,h\}$ is not a $\gamma$-set of T, c and g have a common neighbour $l\notin N\left[a\right]\cup N\left[b\right]$.

Note that in the case they exist, $i\notin \{j,k,l\}$ and $k\ne l$. If $e\notin \{a,b\}$ and $g\notin \{b,c\}$, then $aclgkbjei$ is a cycle in T, contradicting that T is a tree. Hence, by symmetry, we may assume either $e=a$ or $e=b$.

Assume first that $e=a$. Then as a and b are distinct, $b\ne e$. Therefore, from above $a=e$ and b have a common neighbour j. Since $Y=(W-\{a,b\left\}\right)\cup \{c,d\}$ is a $\gamma$-set of T, it must be that $j=c$ (if $j\sim c$, then $ajc$ is a 3-cycle in T). If $b\ne g$ and $c\ne g$, then as $k\ne c$, $bclgk$ is a cycle in T, which contradicts that T is a tree. If $g=b$, as $b\in W$ and $c\notin W$, $c\ne g.$ From above c and $g=b$ have a common neighbour, but c and b are adjacent, contradicting that T is a tree. If $c=g$, then the path $UWXV$ in G corresponds to a swap of f and a, followed by a swap of a and c, followed by a swap of c and h. This corresponds to swaps of the four distinct vertices which induce a path $fach$ in T and hence f and h are distance 3 apart in T. By Observation 1, $pn(f,U)=pn(a,W)=pn(c,X)=pn(h,V)$, but no vertex is in the closed neighbourhood of both f and h, a contradiction.

Otherwise, assume $e=b$. Then as a and b are distinct, $a\ne e$. Therefore from above, a and $b=e$ have a common neighbour, and since Y is a $\gamma$-set, it must be d. If $b\ne g$ and $c\ne g$, then either $ackglbd$ is a cycle in T or contains a cycle in T, which contradicts that T is a tree. If $b=g$, then $c\ne g$. So from above c and $g=b$ have a common neighbour l. As $l\notin N\left[b\right]$, $l\ne d$ so $aclbd$ is a cycle in T, contradicting that T is a tree. If $g=c$, then $g\ne b$. From above b and $g=c$ have a common neighbour k. As $k\notin N\left[c\right]$, $k\ne a$ so $ackbd$ is a cycle in T, contradicting that T is a tree. The result follows. □

While the evidence presented in this section is not conclusive, it highlights that locally, 4-cycles interact similarly to how 4-cycles interact in Cartesian Product graphs.

4.3. 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 γ-graph of a tree T, S be a stem of G, $L_1,L_2,\dots ,L_k$ be the leaves of S, and $G^{\prime }=G-\{L_1,L_2,\dots ,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,\dots ,y_k\in V\left(T\right)-S$ so that $x\sim y_i$ and $L_i=(S-\left\{x\right\})\cup \left\{y_i\right\}$ for $i=1,2,\dots 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 γ-graph of a tree T, S be a stem of G, $L_1,L_2,\dots ,L_k$ be the leaves of S, and $G^{\prime }=G-\{L_1,L_2,\dots ,L_k\}$. If ${deg}_{G^{\prime }}\left(S\right)\ge 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,\dots ,y_k\in V\left(T\right)-S$ so that $x\sim y_i$ and $L_i=(S-\left\{x\right\})\cup \left\{y_i\right\}$ for $i=1,2,\dots 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 $\left\{x\right\}\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 }}\left(S\right)\ge 3$, if x has no S-external private neighbour, then $\left|Z\right|\ge 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 $\left|Z\right|\ge 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-\left\{x\right\})\cup \left\{w_i\right\}$ is a $\gamma$-set of T in $G^{\prime }$ adjacent to S. Let $e_i=S{U}_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\notin S$ so that $a\sim z_1$ and $W=(S-\left\{z_1\right\})\cup \left\{a\right\}$ 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\notin w_1$. Consider the 4-cycle $e_2\square e$. 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\ne 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 $\left|Z\right|={deg}_{G^{\prime }}\left(S\right)\ge 3\ge 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 }}\left(S\right)\ge 3$, $\left|Z\right|={deg}_{G^{\prime }}\left(S\right)\ge 3\ge 2$. For the result we require that $\left|Z\right|\ge 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 γ-graph of a tree T, S be a stem of G, $L_1,L_2,\dots ,L_k$ be the leaves of S, and $G^{\prime }=G-\{L_1,L_2,\dots ,L_k\}$. If ${deg}_{G^{\prime }}\left(S\right)\ge 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,\dots ,v_n)$, where $v_i\in V\left(G_i\right)$ for $i=1,2,\dots ,n$.

Corollary 4.

Let G be a γ-graph of a tree T, S be a stem of G, $L_1,L_2,\dots ,L_k$ be the leaves of S, and $G^{\prime }=G-\{L_1,L_2,\dots ,L_k\}$. If ${deg}_{G^{\prime }}\left(S\right)\ge 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,\dots ,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,\dots ,y_k\in V\left(T\right)-S$ so that $x\sim y_i$ and $L_i=(S-\left\{x\right\})\cup \left\{y_i\right\}$ for $i=1,2,\dots 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 }^{†}(G,v)$ denote the maximum number of edges incident with v with no pair of edges part of the same 4-cycle. We conclude by providing two additional tools to determine if graphs with stems are $\gamma$-graphs.

Lemma 14.

Let G be a γ-graph of a tree T, S be a stem of G, $L_1,L_2,\dots ,L_k$ be the leaves of S, and $G^{\prime }=G-\{L_1,L_2,\dots ,L_k\}$. If ${deg}_{G^{\prime }}\left(S\right)>2{\alpha }^{†}(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-\left\{x\right\})\cup \left\{y_j\right\}$ (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 }^{†}(G^{\prime },S)$ times, so ${deg}_T\left(x\right)\le k+{\alpha }^{†}(G^{\prime },S)$. Let $\left\{x\right\}\cup Z$ be the set of vertices that can be swapped from S. Then ${deg}_{G^{\prime }}\left(S\right)=(de{g}_T\left(x\right)-k)+\left|Z\right|$. It can be shown, as in previous proofs, each $z\in Z$ has a distinct common neighbour with x in $G^{\prime }$, so $\left|Z\right|\le (de{g}_T\left(x\right)-k)$ and hence ${deg}_{G^{\prime }}\left(S\right)\le 2(de{g}_T\left(x\right)-k)\le 2{\alpha }^{†}(G^{\prime },S)$, which is a contradiction. Hence, $G^{\prime }$ is a Cartesian product graph. □

Proposition 8.

Let G be the γ-graph of a tree T, S be a stem of G, $L_1,L_2,\dots ,L_k$ be the leaves of S, and $G^{\prime }=G-\{L_1,L_2,\dots ,L_k\}$. If ${deg}_{G^{\prime }}\left(S\right)=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-\left\{x\right\})\cup \left\{y_j\right\}$ (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 }}\left(S\right)\le 2{\alpha }^{†}(G^{\prime },S)$ and hence ${\alpha }^{†}(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 }\left(\gamma \right)$.

As ${\alpha }^{†}(G^{\prime },S)=1$, it follows from Proposition 2 only one swap in $G^{\prime }$ can use x, so ${deg}_{T^{\prime }}\left(x\right)=1$. If z is the other swap possible from S, then x and z have a common neighbour w, and $pn(z,S)=\left\{v\right\}$. Hence we may assume without loss of generality that the neighbours of S are $P=(S-\{z\left\}\right)\cup \left\{v\right\}$ and $R=(S-\{x\left\}\right)\cup \left\{w\right\}$. By Proposition 2, $Q=(S-\{x,z\left\}\right)\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\notin N_{T_1+T_2}\left[A\right]$, then $x\notin N_{T^{\prime }}\left[A\right]$, which contradicts that A is a $\gamma$-set of $T^{\prime }$. Hence, $N_{T_1+T_2}\left[A\right]=V\left(T^{\prime }\right)-\left\{z\right\}$ 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)=\left\{v\right\}$, it follows that $O=(S-\{x,z\left\}\right)\cup \{w,t\}$ is a $\gamma$-set of $T^{\prime }$. Hence, $O=(Q-\{v\left\}\right)\cup \left\{t\right\}$ 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\left\}\right)\cup \left\{x\right\}$ is not a $\gamma$-set of $T^{\prime }$, and O does not form a 4-cycle with R, as $(R-\{v\left\}\right)\cup \left\{t\right\}$ is not a minimal dominating set ($v\notin 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$. Therefore, $G^{\prime }\cong T^{\prime }\left(\gamma \right)\cong (T_1+T_2)\left(\gamma \right)\cong T_1\left(\gamma \right)\square T_2\left(\gamma \right)$, which is a contradiction. □