Menu
Let \( G \) be an undirected graph. A \textit{vertex tree cover} of \( G \) is a collection of trees such that every vertex of \( G \) is incident with at least one tree. Similarly, an edge tree cover is a collection of trees such that every edge of \( G \) is contained in at least one tree. The tree cover number is defined as the minimum number of trees required in such a cover. In this paper, we demonstrate that when considering specific types of tree covers, only vertex permutations act as linear operators that preserve the tree cover number of \( G \).
The tree cover number of a multigraph has been of interest lately due to it being a lower bound on the maximum nullity of outer planar graphs, and that bound is conjectured to be true for all multigraphs[1-4]. Our interest here is restricted to simple loopless undirected graphs, so below we restrict our definitions, etc. to this case.
Let \({\mathcal G}_n\) denote the set of all simple loopless graphs on the vertex set \(V=\{v_1,v_2,\dots,v_n\}\). A \(k\)-tree in \({\mathcal G}_n\) is an acyclic graph with \(n-k\) isolated vertices and is a connected graph on the \(k\) nonisolated vertices. So an \(n\)-tree is a connected acyclic graph.
Concepts of connectedness, component, isolated vertex, etc. are as in [5]. Let \(U\) be a subset of \(V\). Given a graph \(G\in{\mathcal G}_n\), the subgraph induced by \(U\) is the graph in \({\mathcal G}_n\)whose edge set is the subset of the edge set of \(G\) consisting of all edges whose incident vertices are in \(U\). Because we concider only loopless graphs, any graph induced by a single vertex is an isolated vertex.
Let \(G\in{\mathcal G}_n\). Let \(S(G)\) denote the set of all real symmetric matrices \((a_{i,j})\) satisfying:
\(a_{i,j}=0\) if \(i\neq j\) and \(v_i\) and \(v_j\) are nonadjacent,
\(a_{i,j} \ne 0\) if \(v_i\) and \(v_j\) are adjacent, and
\(a_{i,j}\in \Re\) if \(i=j\) .
The maximum nullity of \(G\) is defined to be \[M(G)=\max\{\hbox{null}(A): A\in S(G)\}.\] The maximum nullity of a graph is equivalent to the maximum multiplicity of an eigenvalue among all matrices in \(S(G)\).
In linear algebra, vector spaces are of primary interest. In this article our approach is via linear algebraic techniques. 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 by the Boolean semiring, where \(1+1=0\) 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 at most 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 conneted, an \(n\)-tree. A \(k\)-tree is a tree with the one nontrivial component connecting \(k\) vertices.
An isolated vertex is a tree on one vertex so in \({\mathcal G}_n\), the edgeless graph is a 1-tree. An edge graph, \(E = (V, E(E))\), is a graph where \(E(E)\) is a singleton and forms a 2-tree.
First we must specify which type of cover: a vertex cover or an edge cover. Let \(G\in {\mathcal G}_n\). A set of graphs in \({\mathcal G}_n\) is a vertex cover of \(G\) if the set of vertices incident with at least one of the edges of one of those graphs contains the set of vertices incident with an edge of \(G\). An edge cover of \(G\) is a set of graphs the union of whose edge sets contains the edge set of \(G\).
There are six concepts easily identified, the first three are vertex covers, the last three are edge covers:
A set of \(n\)-trees covering the vertices of \(G\). A minimal cover always consists of one (arbitrary) \(n\)-tree.
A set of subtrees of the graph covering all \(n\) vertices of the graph. The minimum cardinality of these sets labeled \(\tau_{stv}(G)\) is the subtree vertex cover number of \(G\).
A set of induced subtrees of the graph covering all \(n\) vertices of the graph. The minimum cardinality of these sets labeled \(\tau_{itv}(G)\) is the induced subtree vertex cover number of \(G\).
A set of \(n\)-trees covering the edges of \(G\). The minimum cardinality of these sets labeled \(\tau_{nte}(G)\) is the \(n\)-tree edge cover number of \(G\).
A set of subtrees of the graph covering the edges of the graph. The minimum cardinality of these sets labeled \(\tau_{ste}(G)\) is the subtree edge cover number of \(G\).
A set of induced subtrees of the graph covering the edges of the graph. The minimum cardinality of these sets labeled \(\tau_{ite}(G)\) is the induced subtree edge cover number of \(G\).
Let \(\tau =\tau_{stv}\). Then, \(\tau(G)=n\) if and only if \(G=\overline{K_n}\), the edgeless graph. \(\tau(G)=n-1\) if and only if \(G\) is either an edge graph. Proof: Suppose \(G\) has \(q\) non trivial components. Then, the tree covering number of each of those components is one less than the number of vertices of the nontrivial component. That is \(\tau(G)\leq n-q\). It follows that if \(\tau(G)=n-1\), G has one nontrivial component, which must be either an edge graph. Further, \(\tau(G)=1\) if and only if \(G\) is a connected graph on \(n\) vertices.
Let \(\tau =\tau_{itv}\) Then, \(\tau(G)=n\) if and only if \(G=\overline{K_n}\), the edgeless graph. \(\tau(G)=n-1\) if and only if \(G\) is either an edge graph or a 3-cycle. Proof Hence the proof is similar to as above. Further, \(\tau(G)=1\) if and only if \(G\) is an \(n\)-tree.
Some easily verified trlationships between various vertex tree cover numbers are: \[\tau_{ntv}(G)\leq \tau_{stv}(G)\leq \tau_{itv}(G)\leq n\] for any \(G\in{\mathcal G}_n\).
If \(H\) is any forest, then \(\tau_{nte}(H) = 1\) because adding an edge between two components reduces the number of components by one. Repeating this process eventually results in a single tree that spans all \(n\) vertices, thereby dominating \(H\). Thus, \(\tau_{nte}(H) = 1\). Further, if \(D\) is any \(k\)-cycle then \(\tau_{nte}(D)=2\). Note also \(\tau_{nte}(G)\) is the maximum of the edge tree cover of the components of \(G\).
Some easily verified relationships between various edge tree cover numbers are: \[\tau_{nte}(G)\leq \tau_{ste}(G)\leq \tau_{ite}(G)\leq \tau_{ite}(K_n)={n\choose 2}\] for any \(G\in{\mathcal G}_n\). Further, \[\tau_{ntv}(G)\leq \tau_{nte}(G), \tau_{stv}(G)\leq \tau_{ste}(G)\hbox{ and } \tau_{itv}(G)\leq \tau_{ite}(G)\] for any \(G\in{\mathcal G}_n\).
The following results will be used in the sequel.
Lemma 1. [6, 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}\).
In this subsection, let \(\tau = \tau_{itv}\).
Lemma 2. If \(E\), \(F\), and \(H\) are edge graphs and \(G=E\cup F\cup H\) is not a three cycle, then \(\tau(G) = n-3\).
Proof. There are only 5 possible configurations for \(G=E\cup F\cup H\): a 3-cycle; a 3-star; a 3-path; a 2-star and one vertex disjoint edge; or three vertex disjoint edges. The first has induced tree cover number \(n\), the others all have induced tree cover number \(n-3\). ◻
Suppose that \(T(G)=O\). Then, if \(G \neq O\), \(\tau(G)\neq n\) while \(\tau(T(G))=n\), a contradiction. Thus \(T\) is nonsingular. Recall that \(T\) being nonsingular does not imply invertibility as in the case of vector spaces over fields, it only means the only thing mapped to zero is zero. Thus, we must prove invertibility:
Lemma 3. If \(T:{\mathcal G}_n\to{\mathcal G}_n\) be a linear operator that preserves \(\tau_{itv}\), then \(T\) is bijective on the set of edge graphs, and consequently is bijective on \({\mathcal G}_n\).
Proof. 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 forms a tree. Then, \(\tau(E_1 \cup E_2 \cup \dots \cup E_{n-1}) = 1,\) which implies that \(\tau(T(E_1 \cup E_2 \cup \dots \cup E_{n-1})) = 1.\) Thus, \(T(E_1 \cup E_2 \cup \dots \cup E_{n-1})\) is a tree. However, this means that the image of one of the edges must be dominated by the union of the images of the preceding edges. Therefore, suppose \(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}),\) which is a contradiction, since \(\tau(E_1 \cup E_2 \cup \dots \cup E_{n-1}) = 1 \quad \text{and} \quad \tau(E_1 \cup E_2 \cup \dots \cup E_{n-2}) = 2.\)Thus, the image of an edge graph is itself an edge graph.
Now, let \(E\) and \(F\) be edge graphs and suppose that \(T(E)=T(F)\). Let \(H\) be a tree dominating \(E\cup F\). Then, \(T(H)=T(H\backslash F)\) since \(T(F)=T(E)\). But \(\tau(H)=1\) while \(\tau(H\backslash F)=2\), a contradiction. Thus \(T\) is bijective on the set of edge graphs. It follows that \(T\) is bijective. ◻
Lemma 4. If \(T:{\mathcal G}_n\to{\mathcal G}_n\) be a linear operator that preserves \(\tau_{itv}\), 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 a 3-cycle. Then \(T(E\cup F\cup H)\) is a graph of three edges that is not a 3-cycle. Thus, by Lemma 2, \(\tau(T(E\cup F\cup H))=n-3\) while \(\tau(E\cup F\cup H) = n-1\), a contradiction. That is \(T\) preserves 2-stars. ◻
Theorem 1. If \(T:{\mathcal G}_n\to{\mathcal G}_n\) be a linear operator that preserves \(\tau_{itv}\), then \(T\) is a vertex permutation.
Proof. By Lemma 3 \(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 4 \(T\) preserves 2-stars. By Lemma 4 \(T\) is a vertex permutation. ◻
In this subsection, let \(\tau = \tau_{stv}\).
Lemma 5. If \(E\), \(F\), and \(H\) are edge graphs and \(G=E\cup F\cup H\) is not a three cycle, then \(\tau(G) = n-3\). If \(G\) is a 3-cycle, \(\tau(G)=n-2\).
Proof. There are only 5 possible configurations for \(G=E\cup F\cup H\): a 3-cycle; a 3-star, a 3-path; a 2-star and one vertex disjoint edge; or three vertex disjoint edges. The first has subtree vertex cover number \(n-2\), the others all have subtree vertex tree cover number \(n-3\). ◻
Suppose that \(T(G)=O\). Then, if \(G \neq O\), \(\tau(G)\neq n\) while \(\tau(T(G))=n\), a contradiction. Thus \(T\) is nonsingular.
Lemma 6. If \(T:{\mathcal G}_n\to{\mathcal G}_n\) be a linear operator that preserves \(\tau_{stv}\), then \(T\) is bijective on the set of edge graphs, and consequently is bijective on \({\mathcal G}_n\).
Proof. 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. Then \(\tau(E_1\cup E_2\cup \dots \cup E_{n-1})=1\), so that \(\tau(T(E_1\cup E_2\cup \dots \cup E_{n-1}))=1.\) Thus, \(T(E_1\cup E_2\cup \dots \cup E_{n-1})\) is a tree. But then, the image of one of the edges must be dominated by the union of the images of the previous 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})\), a contradiction since \(\tau(E_1\cup E_2\cup \dots \cup E_{n-1})=1\) and \(\tau(E_1\cup E_2\cup \dots \cup E_{n-2})=2\). 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 a tree dominating \(E\cup F\). Then, \(T(H)=T(H\backslash F)\) since \(T(F)=T(E)\). But \(\tau(H)=1\) while \(\tau(H\backslash F)=2\), a contradiction. Thus \(T\) is bijective on the set of edge graphs. It follows that \(T\) is bijective. ◻
Lemma 7. If \(T:{\mathcal G}_n\to{\mathcal G}_n\) is a linear operator that preserves \(\tau_{stv}\), 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. Then \(T(E\cup F\cup H)\) is a graph of three edges that is not a 3-cycle. Thus, by Lemma 5, \(\tau(T(E\cup F\cup H))=n-3\) while \(\tau(E\cup F\cup H) = n-1\), a contradiction. That is \(T\) preserves 2-stars. ◻
Theorem 2. If \(T:{\mathcal G}_n\to{\mathcal G}_n\) is a linear operator that preserves \(\tau_{stv}\), then \(T\) is a vertex permutation.
Proof. By Lemma 6 \(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 7 \(T\) preserves 2-stars. By Lemma 1 \(T\) is a vertex permutation. ◻
In this subsection, let \(\tau = \tau_{nte}\).
Lemma 8. If \(E\), \(F\), and \(H\) are edge graphs and \(G=E\cup F\cup H\) is not a three cycle, then \(\tau(G) = 1\). If \(G\) is a 3-cycle, \(\tau(G)=2\).
Proof. There are only 5 possible configurations for \(G=E\cup F\cup H\): a 3-cycle; a 3-star, a 3-path; a 2-star and one vertex disjoint edge; or three vertex disjoint edges. The first has \(n\)-tree edge cover number \(2\), the others all have \(n\)-tree edge tree cover number \(1\). ◻
Suppose that \(T(G)=O\). Then, \(T(E)=O\) for some edge graph \(E\). If \(F\) and \(H\) are edge graphs such that \(E\cup F\cup H\) is a 3-cycle, then \(\tau(F\cup H)=1\) while \(\tau(E\cup F\cup H)=2\). But then, \(2= \tau(T(E\cup F\cup H)) = \tau(T(F\cup H))=1\), a contradiction. Thus \(T\) is nonsingular.
Lemma 9. If \(T:{\mathcal G}_n\to{\mathcal G}_n\) is a linear operator that preserves \(\tau_{nte}\), then \(T\) is bijective on the set of edge graphs, and consequently is bijective on \({\mathcal G}_n\).
Proof. Suppose that the image of an edge graph, \(E\), has more than one edge. Let \(E=E_1\) and \(E_1, E_2, \dots, E_{n-1}\) be \({n-1}\) edge graphs whose union is an \(n\)-tree. Let \(H=E_1\cup E_2\cup \dots \cup E_{n-1}\). Then \(T(H)=T(H\backslash F)\) for some edge \(F\) in \(H\). Now, \(H\backslash F\) is a forest with two components.
Let \(C\) be an edge connecting those two components, with \(C\neq F\). Then, \(\tau_{nte}((H\backslash F)\cup C)=1\) while \(\tau_{nte}(H\cup C)=2\). However, \(T((H\backslash F)\cup C)=T(H\backslash F)\cup T(C)=T(H)\cup C\), which contradicts the fact that \(T\) preserves \(\tau_{nte}\). Thus, \(T\) maps edge graphs to edge graphs.
Next, let \(E\) and \(F\) be edge graphs, and suppose that \(T(E)=T(F)\). Let \(C\) be a cycle dominating \(E\cup F\). Then, \(T(C)=T(C\backslash F)\) since \(T(F)=T(E)\). But \(\tau_{nte}(C)=2\) while \(\tau_{nte}(C\backslash F)=1\), a contradiction. Thus, \(T\) is bijective on the set of edge graphs.
It follows that \(T\) is bijective. ◻
Lemma 10. If \(T:{\mathcal G}_n\to{\mathcal G}_n\) is a linear operator that preserves \(\tau_{nte}\), 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. Then \(T(E\cup F\cup H)\) is a graph of three edges that is not a 3-cycle. Thus, by Lemma 8, \(\tau(T(E\cup F\cup H))=1\) while \(\tau(E\cup F\cup H) = 2\), a contradiction. That is \(T\) preserves 2-stars. ◻
Theorem 3. If \(T:{\mathcal G}_n\to{\mathcal G}_n\) is a linear operator that preserves \(\tau_{nte}\), then \(T\) is a vertex permutation.
Proof. By Lemma 9 \(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 10\(T\) preserves 2-stars. By Lemma 1 \(T\) is a vertex permutation. ◻
In this subsection, let \(\tau = \tau_{ste}\).
Lemma 11. If \(E\), \(F\), and \(H\) are edge graphs and \(G=E\cup F\cup H\) is not a three cycle, then \(\tau(G) = n-3\).
Proof. There are only 5 possible configurations for \(G=E\cup F\cup H\): a 3-cycle; a 3-star, a 3-path; a 2-star and one vertex disjoint edge; or three vertex disjoint edges. The first has subtree vertex cover number \(n-1\), the others all have subtree vertex tree cover number \(n-3\). ◻
Suppose that \(T(G)=O\). Then, if \(G \neq O\), \(\tau(G)\neq n\) while \(\tau(T(G))=n\), a contradiction. Thus \(T\) is nonsingular.
Lemma 12. If \(T:{\mathcal G}_n\to{\mathcal G}_n\) be a linear operator that preserves \(\tau_{ste}\), then \(T\) is bijective on the set of edge graphs, and consequently is bijective on \({\mathcal G}_n\).
Proof. 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. Then \(\tau(E_1\cup E_2\cup \dots \cup E_{n-1})=1\), so that \(\tau(T(E_1\cup E_2\cup \dots \cup E_{n-1}))=1.\) Thus, \(T(E_1\cup E_2\cup \dots \cup E_{n-1})\) is a tree. But then, the image one of the edges must be dominated by the union of the images of the previous 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})\), a contradiction since \(\tau(E_1\cup E_2\cup \dots \cup E_{n-1})=1\) and \(\tau(E_1\cup E_2\cup \dots \cup E_{n-2})=2\). 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 a tree dominating \(E\cup F\). Then, \(T(H)=T(H\backslash F)\) since \(T(F)=T(E)\). But \(\tau(H)=1\) while \(\tau(H\backslash F)=2\), a contradiction. Thus \(T\) is bijective on the set of edge graphs. It follows that \(T\) is bijective. ◻
Lemma 13. If \(T:{\mathcal G}_n\to{\mathcal G}_n\) be a linear operator that preserves \(\tau_{ste}\), 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. Then \(T(E\cup F\cup H)\) is a graph of three edges that is not a 3-cycle. Then, \(\tau(T(E\cup F\cup H)= n-3\) while \(\tau(E\cup F\cup H)= n-1\), contradicting that \(T\) preserves \(\tau_{ste}\). That is \(T\) preserves 2-stars. ◻
Theorem 4. If \(T:{\mathcal G}_n\to{\mathcal G}_n\) be a
linear operator that preserves \(\tau_{ste}\), then \(T\) is a vertex
permutation.
Proof. By Lemm 12 \(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 13 \(T\) preserves 2-stars. By Lemma 1 \(T\) is a vertex permutation. ◻
In this subsection, let \(\tau = \tau_{ite}\).
Lemma 14. If \(E\), \(F\), and \(H\) are edge graphs and \(G=E\cup F\cup H\) is not a three cycle, then \(\tau(G) = n-3\).
Proof. There are only 5 possible configurations for \(G=E\cup F\cup H\): a 3-cycle; a 3-star, a 3-path; a 2-star and one vertex disjoint edge; or three vertex disjoint edges. The first has subtree vertex cover number \(n-1\), the others all have subtree vertex tree cover number \(n-3\). ◻
Suppose that \(T(G)=O\). Then, if \(G \neq O\), \(\tau(G)\neq n\) while \(\tau(T(G))=n\), a contradiction. Thus \(T\) is nonsingular.
Lemma 15. If \(T:{\mathcal G}_n\to{\mathcal G}_n\) be a linear operator that preserves \(\tau_{ite}\), then \(T\) is bijective on the set of edge graphs, and consequently is bijective on \({\mathcal G}_n\).
Proof. 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. Then \(\tau(E_1\cup E_2\cup \dots \cup E_{n-1})=1\), so that \(\tau(T(E_1\cup E_2\cup \dots \cup E_{n-1}))=1.\) Thus, \(T(E_1\cup E_2\cup \dots \cup E_{n-1})\) is a tree. But then, the image one of the edges must be dominated by the union of the images of the previous 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})\), a contradiction since \(\tau(E_1\cup E_2\cup \dots \cup E_{n-1})=1\) and \(\tau(E_1\cup E_2\cup \dots \cup E_{n-2})=2\). 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 a tree dominating \(E\cup F\). Then, \(T(H)=T(H\backslash F)\) since \(T(F)=T(E)\). But \(\tau(H)=1\) while \(\tau(H\backslash F)=2\), a contradiction. Thus \(T\) is bijective on the set of edge graphs. It follows that \(T\) is bijective. ◻
Lemma 16. If \(T:{\mathcal G}_n\to{\mathcal G}_n\) be a linear operator that preserves \(\tau_{ite}\), 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. Then \(T(E\cup F\cup H)\) is a graph of three edges that is not a 3-cycle. Then, \(\tau(T(E\cup F\cup H)= n-3\) while \(\tau(E\cup F\cup H)= n-1\), contradicting that \(T\) preserves \(\tau_{ite}\). That is \(T\) preserves 2-stars. ◻
Theorem 5. If \(T:{\mathcal G}_n\to{\mathcal G}_n\) be a linear operator that preserves \(\tau_{ite}\), then \(T\) is a vertex permutation.
Proof. By Lemma 15 \(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 16, \(T\) preserves 2-stars. By Lemma 1, \(T\) is a vertex permutation. ◻
Barioli, F., Fallat, S. M., Mitchell, L. H. and Narayan, S. K., 2011. Minimum semidefinite rank of outerplanar graphs and the tree cover number. Electronic Journal of Linear Algebra, 22, pp.10–21.
Domagalski, R. and Narayan, S. K., 2020. Tree cover number and maximum semidefinite nullity of some graph classes. Electronic Journal of Linear Algebra, 36, pp.678–693.
Fallat, S. M. and Hogben, L., 2007. The minimum rank of symmetric matrices described by a graph: A survey. Linear Algebra and Its Applications, 426(2-3), pp.558–582.
Bondy, J. A. and Murthy, U. S. R., 2008. Graph Theory (Graduate Texts in Mathematics). Springer.
Beasley, L. B. and Pullman, N. J., 1990. Linear operators preserving properties of graphs. Congressus Numerantium, 70, pp.105–112.