Let\(G\) be an undirected graph. A tree partition of\(G\) is a set of trees whose edge sets are disjoint and whose union is the edge set of\(G\). The minimum cardinality of such a tree partition is called the tree partition number of\(G\). We show that for various types of trees allowed in the tree partition, that the only linear operators that preserve the tree partition number are vertex permutations.
In [1] tree cover numbers of graphs and their linear preservers were investigated. The induced tree vertex cover number is conjectured to be a lower bound on the maximum nullity of the graph, see [3, 4]. Recently, Chalise et al. [6], and Gnang, [5] investigated tree partitions in their study of the Ringel-Kotzig-Rosa and the graceful tree conjectures. In this article we consider tree partitions of graphs and show that the only linear preservers of the tree partition number are vertex permutations.
In linear algebra, vector spaces are of primary interest. The set of graphs, \({\mathcal G}_n\), each with the fixed vertex set, \(V\), forms a Boolean vector space where addition of graphs is the union (of the edge sets) and scalar multiplication is via the Boolean semiring, where 1+1=1 and all other arithmetic is as usual (there is no subtraction or negatives), the zero is the edgeless graph. Since we will be dealing only with graphs all having the same vertex set, we must define a tree as follows: A forest is an acyclic graph and a tree is a forest with exactly one nontrivial component. The usual definition of a tree, being an acyclic connected graph would in our context, mean all trees had \(n-1\) edges and all \(n\) vertices connected, an \(n\)-tree. A \(k\)-tree is a tree with the one nontrivial component connecting \(k\) vertices. \(k\)-trees exist for \(2\leq k\leq n\) only. An edge graph, \(E=(V,E(E))\) is the graph with \(E(E)\) a singleton, a \(2\)-tree.
Let \(G\in {\mathcal G}_n\). A set, \(Q\), of graphs in \({\mathcal G}_n\) is an edge partition of \(G\) if the edge sets of the members of \(Q\) are disjoint and their union is the edge set of \(G\). In this article we will be primarily interested when \(Q\) is a set of trees.
There are two concepts easily identified as tree edge partitions:
(a) A set of subtrees of the graph partitioning the edges of the graph. The minimum cardinality of these sets labeled \(\sigma_s(G)\) is the subtree edge partition number of \(G\).
(b) A set of induced subtrees of the graph partitioning the edges of the graph. The minimum cardinality of these sets labeled \(\sigma_i(G)\) is the induced subtree edge partition number of \(G\).
A graph, \(G\) is said to be decomposed (partitioned) by a tree, \(T\), if a set of graphs, each isomorphic to \(T\), is an edge partition of the graph \(G\).
Let \(T\) be a tree in \({\mathcal G}_n\) and let \(\Gamma_T\) denote the set of all graphs in \({\mathcal G}_n\) that are partitioned by \(T\). Clearly, a \(k\)-tree can decompose a graph \(G\) only if \(k-1\) divides the number of edges in \(G\).
(a) Let \(T\) be a 2-tree, i.e. an edge graph, then, \(\Gamma_T={\mathcal G}_n\).
(b) If \(T\) is a 2-star (a 2-path) then \(\Gamma_T\) is the set of all graphs, \(G\), with the property that each connected block of \(G\) has an even number of edges.
(c) If \(T\) is either a 3-star or a 3-path, \(\Gamma_T\) is not easily described, The 3-path is not partitioned be the 3-star and the 3-star is not partitioned by the 3-path.
An interesting problem would be to show that all graphs, each component of which has a multiple of \(k\) edges is partitioned be some set of \(k\)-trees or \(k\)-edge graphs. Or provide counter examples.
The following lemmas will be used in the sequel.
Lemma 2.1. Let \(T:{\mathcal G}_n \to{\mathcal G}_n\) be a linear operator. Then the following are equivalent:
\(T\) is injective;
\(T\) is surjective;
\(T\) is bijective.
Proof. This follows from the fact that \({\mathcal G}_n\) is finite. ◻
Lemma 2.2. [2, Lemma 2.2] If \(T : {\mathcal G}_n \to {\mathcal G}_n\) is bijective, preserves \(|E(G)|\), and maps 2-stars to 2-stars then T is a vertex permutation.
Let \(O\) denote the edgeless graph, \(\overline{K_n}\).
Our investigation requires investigating preservers of \(\sigma_s\) and \(\sigma_i\) separately.
Lemma 2.3. If \(T:{\mathcal G}_n \to{\mathcal G}_n\) is a linear operator that preserves \(\sigma_s\), then \(T\) is nonsingular.
Proof. Suppose that \(T(G)=O\) for some graph \(G\) and let \(H\) be an edge graph dominated by \(G\), so that \(T(H)=O\). Let \(E\) and \(F\) be edge graphs such that \(E\cup F\cup H\) is a 3-cycle. Then \(\sigma_s(E\cup F\cup H)=2\) while \(\sigma_s(E\cup F)=1\), But \(T(E\cup F)=T(E\cup F\cup H)\), a contradiction since \(T\) preserves \(\sigma_s\). Thus \(T\) is nonsingular. ◻
Recall that \(T\) being nonsingular does not imply invertibility or bijectivity as in the case of vector spaces over fields, it only means the only thing mapped to zero is zero. Thus, we must prove bijectivity:
Lemma 2.4. If \(T:{\mathcal G}_n \to{\mathcal G}_n\) is a linear operator that preserves \(\sigma_s\), then \(T\) is bijective on the set of edge graphs, and consequently is bijective on \({\mathcal G}_n\).
Proof. By Lemma 2.1 we only need show that \(T\) is injective. Suppose that the image of an edge graph, \(E\), has more than one edge. Let \(E=E_1, E_2, \dots ,E_{n-1}\) be \(n-1\) edge graphs whose union is a tree. But then, the image one of the edges must be dominated by the union of the images of the previous edges since a tree has at most \(n-1\) edges. Thus, say \(T(E_{n-1})\) is dominated by \(T(E_1\cup E_2\cup \dots \cup E_{n-2})\), so that \(T(E_1\cup E_2\cup \dots \cup E_{n-1})=T(E_1\cup E_2\cup \dots \cup E_{n-2})\). Then \(\sigma_s(E_1\cup E_2\cup \dots \cup E_{n-1})=1\), so that \(\sigma_s(T(E_1\cup E_2\cup \dots \cup E_{n-1}))=1.\) Let \(F\) be an edge graph, \(F\neq E_{n-1}\), such that \(E_1\cup E_2\cup \dots \cup E_{n-2}\cup F\) is a tree. Then \(E_1\cup E_2\cup \dots \cup E_{n-1}\cup F\) is not a tree (it must contain a cycle since it has \(n\) edges.) So, \(\sigma_s(E_1\cup E_2\cup \dots \cup E_{n-1}\cup F)=2\) while \(\sigma_s(E_1\cup E_2\cup \dots \cup E_{n-2}\cup F)=1\). But \(T(E_1\cup E_2\cup \dots \cup E_{n-1}\cup F)=T(E_1\cup E_2\cup \dots \cup E_{n-2}\cup F)\) since \(T(E_1\cup E_2\cup \dots \cup E_{n-1})=T(E_1\cup E_2\cup \dots \cup E_{n-2})\), a contradiction since \(T\) preserves \(\sigma_s\). Thus the image of an edge graph is an edge graph.
Now, let \(E\) and \(F\) be edge graphs and suppose that \(T(E)=T(F)\). Let \(H\) be an \(n\)-tree dominating \(E\) and not \(F\). Then, \(T(H)=T(H\cup F)\) since \(T(F)=T(E)\). But \(\sigma_s(H)=1\) while \(\sigma_s(H\cup F)=2\) since \(H\cup F\) must dominate a cycle, a contradiction. Thus \(T\) is injective and hence bijective on the set of edge graphs. It follows that \(T\) is bijective on \({\mathcal G}_n\). ◻
Lemma 2.5. If \(T:{\mathcal G}_n \to{\mathcal G}_n\) be a linear operator that preserves \(\sigma_s\), then \(T\) maps 2-stars to 2-stars.
Proof. Let \(E\cup F\) be a two star and suppose that \(T(E\cup F)\) is not. Then \(T(E\cup F)\) is a vertex disjoint pair of edges. Let \(H\) be the edge graph such that \(E\cup F\cup H\) is 3-cycle so that \(\sigma_s(E\cup F\cup H)= 2\). Then \(T(E\cup F\cup H)\) is a graph of three edges that is not a 3-cycle. Thus \(T(E\cup F\cup H)\) is one of:
(a) three mutually disjoint edges, so that \(\sigma_s(T(E\cup F\cup H))= 3\);
(b) a two path and a disjoint edge so that \(\sigma_s(T(E\cup F\cup H))= 2\); or
(c) a three path so that \(\sigma_s(T(E\cup F\cup H))= 1\).
Since \(T\) preserves \(\sigma_s\), it follows that \(T(E\cup F\cup H)\) is a two path and a disjoint edge. Let \(K\) be an edge graph such that the edge graph \(T(K)\) joins the ends of the two parts of \((T(E\cup F\cup H)\) so that \((T(E\cup F\cup H)\cup T(K)\) is a path. Then, \(\sigma_s(E\cup F\cup H\cup K) \geq 2\) while \(\sigma_s(T(E\cup F\cup H)\cup T(K) =1\), a contradiction. That is \(T\) preserves 2-stars. ◻
Theorem 2.6. If \(T:{\mathcal G}_n \to{\mathcal G}_n\) be a linear operator that preserves \(\sigma_s\), then \(T\) is a vertex permutation.
Proof. By Lemma 2.4 \(T\) is bijective on the set of edge graphs and hence \(|E(T(G))|= |E(G)|\) for all \(G\in{\mathcal G}_n\). By Lemma 2.5 \(T\) preserves 2-stars. By Lemma 2.2, \(T\) is a vertex permutation. ◻
The investigation in this section parallels the above section. We include it for completeness.
Lemma 2.7. If \(T:{\mathcal G}_n \to{\mathcal G}_n\) is a linear operator that preserves \(\sigma_i\), then \(T\) is nonsingular.
Proof. Suppose that \(T(G)=O\) for some edge graph \(G\). Let \(E\) and \(F\) be edge graphs such that \(E\cup F\cup G\) is a 3-cycle. Then \(\sigma_i(E\cup F\cup G)=3\) while \(\sigma_i(E\cup F)=1\), But \(T(E\cup F)=T(E\cup F\cup G)\), a contradiction since \(T\) preserves \(\sigma_i\). Thus \(T\) is nonsingular. ◻
As above recall that \(T\) being nonsingular does not imply invertibility or bijectivity as in the case of vector spaces over fields, it only means the only thing mapped to zero is zero. Thus, we must prove bijectivity:
Lemma 2.8. If \(T:{\mathcal G}_n \to{\mathcal G}_n\) be a linear operator that preserves \(\sigma_i\), then \(T\) is bijective on the set of edge graphs, and consequently is bijective on \({\mathcal G}_n\).
Proof. By Lemma 2.1 we only need show that \(T\) is injective. Suppose that the image of an edge graph, \(E\), has more than one edge. Let \(E=E_1, E_2, \dots ,E_{n-1}\) be \(n-1\) edge graphs whose union is a tree. But then, the image one of the edges must be dominated by the union of the images of the previous edges since a tree has at most \(n-1\) edges. Thus, say \(T(E_{n-1})\) is dominated by \(T(E_1\cup E_2\cup \dots \cup E_{n-2})\), so that \(T(E_1\cup E_2\cup \dots \cup E_{n-1})=T(E_1\cup E_2\cup \dots \cup E_{n-2})\). Then \(\sigma_i(E_1\cup E_2\cup \dots \cup E_{n-1})=1\), so that \(\sigma_i(T(E_1\cup E_2\cup \dots \cup E_{n-1}))=1.\) Let \(F\) be an edge graph, \(F\neq E_{n-1}\), such that \(E_1\cup E_2\cup \dots \cup E_{n-2}\cup F\) is a tree. Then \(E_1\cup E_2\cup \dots \cup E_{n-1}\cup F\) is not a tree (it must contain a cycle since it has \(n\) edges.) So, \(\sigma_i(E_1\cup E_2\cup \dots \cup E_{n-1}\cup F)\geq 2\) while \(\sigma_i(E_1\cup E_2\cup \dots \cup E_{n-2}\cup F)=1\). But \(T(E_1\cup E_2\cup \dots \cup E_{n-1}\cup F)=T(E_1\cup E_2\cup \dots \cup E_{n-2}\cup F)\) since \(T(E_1\cup E_2\cup \dots \cup E_{n-1})=T(E_1\cup E_2\cup \dots \cup E_{n-2})\), a contradiction since \(T\) preserves \(\sigma_i\). Thus the image of an edge graph is an edge graph.
Now, let \(E\) and \(F\) be edge graphs and suppose that \(T(E)=T(F)\). Let \(H\) be an \(n\)-tree dominating \(E\) and not \(F\). Then, \(T(H)=T(H\cup F)\) since \(T(F)=T(E)\). But \(\sigma_i(H)=1\) while \(\sigma_i(H\cup F)\geq 2\) since \(H\cup F\) must dominate a cycle, a contradiction. Thus \(T\) is injective and hence bijective on the set of edge graphs. It follows that \(T\) is bijective on \({\mathcal G}_n\). ◻
Lemma 2.9. If \(T:{\mathcal G}_n \to{\mathcal G}_n\) is a linear operator that preserves \(\sigma_i\), then \(T\) maps 2-stars to 2-stars.
Proof. Let \(E\cup F\) be a 2-star and suppose that \(T(E\cup F)\) is not. Then \(T(E\cup F)\) is a vertex disjoint pair of edges. Let \(H\) be the edge graph such that \(E\cup F\cup H\) is 3-cycle so that \(\sigma_i(E\cup F\cup H)= 3\). Then \(T(E\cup F\cup H)\) is a graph of three edges that is not a 3-cycle. Thus \(T(E\cup F\cup H)\) is one of:
(a) three mutually disjoint edges, so that \(\sigma_i(T(E\cup F\cup H))= 3\);
(b) a two path and a disjoint edge so that \(\sigma_i(T(E\cup F\cup H))= 2\); or
(c) a three path so that \(\sigma_i(T(E\cup F\cup H))= 1\).
Since \(T\) preserves \(\sigma_i\), it follows that \(T(E\cup F\cup H)\) is three mutually disjoint edges. Let \(K\) be an edge graph such that the edge graph \(T(K)\) joins the ends of two of the edges of \(T(E\cup F\cup H)\) so that \(T(E\cup F\cup H)\cup T(K)\) is a three path and an isolated edge. Then, \(\sigma_i(E\cup F\cup H\cup K) \geq 3\) while \(\sigma_i(T(E\cup F\cup H)\cup T(K)) =2\), a contradiction. That is \(T\) preserves 2-stars. ◻
Theorem 2.10. If \(T:{\mathcal G}_n \to{\mathcal G}_n\) be a linear operator that preserves \(\sigma_i\), then \(T\) is a vertex permutation.
Proof. By Lemma 2.8 \(T\) is bijective on the set of edge graphs and hence \(|E(T(G))|= |E(G)|\) for all \(G\in{\mathcal G}_n\). By Lemma 2.9 \(T\) preserves 2-stars. By Lemma 2.2, \(T\) is a vertex permutation. ◻
In this subsection, let \(T\) be a \(k\)-tree, \(k\geq 2\).
Lemma 2.11. If \(L:{\mathcal G}_n \to{\mathcal G}_n\) is a bijective linear map that strongly preserves \(\Gamma_T\) then \(L\) strongly preserves \({\mathcal T}\), the set of all trees in \({\mathcal G}_n\) that are isomorphic to \(T\).
Proof. Since \(L\) is bijective and linear, \(L\) maps edge graphs to edge graphs and preserves the size of the graph. Hence, the image of a tree in \({\mathcal T}\) where \(T\) has \(k\) edges is a graph of \(k\) edges that is partitioned by \(T\). Clearly that image must be a tree isomorphic to \(T\). ◻
If \(T\) is a tree dominating a path of two edges but not dominating a path of three edges then \(T\) is a star graph.
If \(T\) is a tree dominating a path of three edges but not dominating a path of four edges, then \(T\) consists of two stars whose central vertices are connected by an edge. See Figure 1. This is called an \((r,s)\)-double star if the two stars centers are of degrees \(r-1\) and \(s-1\).
If \(T\) is a tree dominating a path of four edges but not dominating a path of five edges, then \(T\) consists of a central star, \(S\), whose noncentral vertices are the central vertices of stars. If the central vertex of the star \(S\) has degree two then, \(T\) consists of two stars whose central vertices are connected by a path of two edges. See Figure 2. This is called an \((r,s)\)-incident pair of star graphs if the two stars centers are of degrees \(r-1\) and \(s-1\). If the central vertex has degree larger than two and at least three of the other stars meet at least two edges, then the graph dominates three mutually independent edges.
Note: No star, \((r,s)\)-double star, or \((r,s)\)-incident pair of star graphs dominate a graph of three mutually independent edges, however, all other trees do dominate a graph of three mutually independent edges.
Lemma 2.12. If \(L:{\mathcal G}_n \to{\mathcal G}_n\) is a linear operator that strongly preserves \(\Gamma_T\), then \(L\) is nonsingular.
Proof. Suppose that \(L(G)=O\) for some graph \(G\). Then \(L(E)=O\) for any edge graph \(E\) dominated by \(G\). Let \(H\) be a tree isomorphic to \(T\) that dominates \(E\). Then \(L(H)=L(H\backslash E)\). But \(H\in\Gamma_T\), while \(H\backslash E \notin\Gamma_T\), a contradiction since \(L\) strongly preserves \(\Gamma_T\). Thus \(L\) is nonsingular. ◻
As above recall that \(L\) being nonsingular does not imply invertibility or bijectivity as in the case of vector spaces over fields, it only means the only thing mapped to zero is zero. Thus, we must prove bijectivity:
Lemma 2.13. If \(L:{\mathcal G}_n \to{\mathcal G}_n\) is a linear operator that strongly preserves \(\Gamma_T\), then \(L\) maps edge graphs to edge graphs.
Proof. Suppose that the image of an edge graph, \(E\), has more than one edge. Let \(E=E_1, E_2, \dots ,E_{k-1}\) be \(k-1\) edge graphs whose union is a \(k\)-tree isomorphic to \(T\). Then, since \(L(E_1\cup E_2\cup \dots \cup E_{k-1})\) must be a \(k\)-tree, the image of some edge, say \(E_{k-1}\), is dominated by the union of the others. That is \(L(E_1\cup E_2\cup \dots \cup E_{k-2})=L(E_1\cup E_2\cup \dots \cup E_{k-1})\). But \(E_1\cup E_2\cup \dots \cup E_{k-2}\notin \Gamma_T\) while \(E_1\cup E_2\cup \dots \cup E_{k-1}\in\Gamma_T\), a contradiction. Thus, \(L\) maps edge graphs to edge graphs. ◻
Lemma 2.14. If \(L:{\mathcal G}_n \to{\mathcal G}_n\) be a linear operator that strongly preserves \(\Gamma_T\), then \(L\) is bijective on the set of edge graphs, and consequently is bijective on \({\mathcal G}_n\).
Proof. By Lemma 2.1 we only need show that \(L\) is injective. By Lemma 2.13 the image of an edge graph is an edge graph.
Now, let \(E\) and \(F\) be edge graphs and suppose that \(L(E)=L(F)\). Let \(H\) be a \(k\)-tree isomorphic to \(L\) that dominates \(E\) and \(F\). So that \(H\in \Gamma_T\) while \(H\backslash F\notin \Gamma_T\). But, \(L(H)=L(H\backslash F)\) since \(L(F)=L(E)\), a contradiction. Thus \(L\) is injective and hence bijective on the set of edge graphs. It follows that \(L\) is bijective. ◻
Lemma 2.15. Let \(T\) be a tree with \(k-1\) edges, a \(k\)-tree. If \(T\) dominates a 5 edge path, or is a star, and if \(L:{\mathcal G}_n \to{\mathcal G}_n\) is a linear operator that strongly preserves \(\Gamma_T\), then \(L\) maps 2-stars to 2-stars.
Proof. Let \({\mathcal T}\) be the set of all graphs isomorphic to \(T\). Since \(L\) is bijective and hence maps edge graphs to edge graphs and preserves the size of the edge set, if \(H\in{\mathcal T}\) then \(L(H)\) is a graph on \(k-1\) edges dominated by some element of \({\mathcal T}\). That is, \(L(H)\) is a tree in \({\mathcal T}\).
Now, if \(T\) is a star then any pair of edges forming a 2-star is dominated by some element of \({\mathcal T}\) and hence is a 2-star.
Suppose \(T\) dominates a 5 edge path, and that \(E\) and \(F\) are edge graphs whose union is a 2-star. If \(L(E\cup F)\) is not a 2-star then \(L(E\cup F)\) is a pair of mutually nonincident edges. Let \(Q\) be the edge graph such that \(E\cup F\cup Q\) is a three cycle. Then \(E\cup F\cup Q\) is not in \(\Gamma_T\). It follows that \(L( E\cup F\cup Q)\) is a 3-edge path, a 2-edge path plus one isolated (nonincident) edge or three mutually nonincident edges. However, each of these 3-edge graphs is dominated by some member of \({\mathcal T}\), a contradiction since \(L\) strongly preserves \(\Gamma_T\). Thus, \(L\) maps 2-stars to 2-stars. ◻
Lemma 2.16. Let \(n\geq 6\) and \(T\) be a tree with \(k-1\) edges, a \(k\)-tree. If \(T\) dominates a 3 edge path but not a 4 edge path, and if \(L:{\mathcal G}_n \to{\mathcal G}_n\) is a bijective linear operator that strongly preserves \(\Gamma_T\), then \(L\) maps 2-stars to 2-stars.
Proof. Let \({\mathcal T}\) be the set of all graphs isomorphic to \(T\). Now, \(L\) is bijective and maps edge graphs to edge graphs and preserves the size of the edge set. Further, \(T\) is an \((r,s)\)-double star. Let \(E\) and \(F\) be edge graphs whose union is a 2-star. Suppose that \(L(E\cup F)\) is not a 2-star, and hence a pair of parallel edges. Let \(H\) be an edge graph in \({\mathcal G}_n\) such that \(L(H)\) is not incident with \(L(E\cup F)\), this is possible when \(n\geq 6\). Then, \(L(E\cup F\cup H)\) is a graph of three mutually independent edges. Now, \(E\cup F\cup H\) is dominated by some \((r,s)\)-double star, but \(L(E\cup F\cup H)\) is not, a contradiction. Thus \(L\) maps 2-stars to 2-stars. ◻
Lemma 2.17. Let \(n\geq 6\) and \(T\) be a tree with \(k-1\) edges, a \(k\)-tree. If \(T\) dominates a 4 edge path but not a 5 edge path, and if \(L:{\mathcal G}_n \to{\mathcal G}_n\) is a bijective linear operator that strongly preserves \(\Gamma_T\), then \(L\) maps 2-stars to 2-stars.
Proof. If \(T\) dominates a 4 edge path but not a 5 edge path, then \(T\) consists of a central star and star graphs centered at each non central vertex of that center star. Suppose the degree of the central vertex is greater than two. Let \(E\) and \(F\) be edge graphs whose union is a 2-star. Suppose that \(L(E\cup F)\) is not a 2-star, and hence a pair of mutually nonincident edges. Let \(G\) be the edge graph such that \(E\cup F\cup G\) is a 3-cycle. Then \(E\cup F\cup G\) is not in any tree in \({\mathcal T}\) and hence \(L(E\cup F\cup G)\) is not in any member of \({\mathcal T}\). It follows that \(L(E\cup F\cup G)\) is a 3-edge path, a 2-edge path plus one isolated (nonincident) edge or three mutually independent edges. If the degree of the central vertex is at least 3, the each of these types of graphs are contained in some member of \({\mathcal T}\), a contradiction, so that the degree of the central vertex is 2 and \(T\) is an \((r,s)\)-incident pair of star graphs. See Figure 2.
Let \({\mathcal T}\) be the set of all graphs isomorphic to \(T\). Here, \(L\) is bijective and maps edge graphs to edge graphs and preserves the size of the edge set. Further, \(T\) is an \((r,s)\)-incident pair of star graphs. Let \(E\) and \(F\) be edge graphs whose union is a 2-star. Suppose that \(L(E\cup F)\) is not a 2-star, and hence a pair of parallel edges. Let \(H\) be an edge graph in \({\mathcal G}_n\) such that \(L(H)\) is not incident with \(L(E\cup F)\), this is possible when \(n\geq 6\). Then, \(L(E\cup F\cup H)\) is a graph of three mutually independent edges. Now, \(E\cup F\cup H\) is dominated in some \((r,s)\)-incident parallel pair of star graphs, but \(L(E\cup F\cup H)\) is not, a contradiction. Thus \(L\) maps 2-stars to 2-stars. ◻
Theorem 2.18. If \(L:{\mathcal G}_n \to{\mathcal G}_n\) is a linear operator that strongly preserves \(\Gamma_T\) and \(n\geq 6\), then \(T\) is a vertex permutation.
Proof. By Lemma 2.14, \(T\) is bijective and by Lemma 2.16, Lemma 2.17, and Lemma 2.15, \(T\) maps 2-stars to 2-stars. By Lemma 2.2, \(T\) is a vertex permutation. ◻