Let \(G\) be an undirected graph. The \(k\)-strong labeling (coloring) number of \(G\), \(\chi_k(G)\), is the minimum number of labels (colors) necessary to label all the vertices of \(G\) so that no two vertices that are exactly of distance \(k\) apart have the same label. \(\chi_1\) is the usual chromatic number. In this article it is shown that any linear operator on the set of graphs on \(n\) vertices thar preserves \(\chi_k\) is a vertex permutation.
Let \(\mathcal{G}_n\) denote the set of all loopless simple undirected graphs on the vertex set \(V=\{v_1, v_2, \dots , v_n\}\). Let \(C\) be a labeling \(C:V\to \{1,2,\dots , n\}\) of the vertex set. For \(G\in\mathcal{G}_n\), we say \(C\) is a \(k\)-strong labeling if given any two vertices \(u,v\in V\) with the distance from \(u\) to \(v\) equal \(k\), we have that \(C(u)\neq C(v)\). Let \(\chi_k:\mathcal{G}_n\to \{1,2,\dots , n\}\) be the minimum cardinality of the labels that are \(k\)-strong labels of \(G\). So, \(\chi_1(G)\) is the chromatic number of \(G\), the fewest number of colors needed to color the vertices so that no two adjacent vertices are the same color. Similarly, \(\chi_2(G)\) is what some authors call the strong coloring number, see [2].
The objective of this article is to investigate the linear operators on \(\mathcal{G}_n\) that preserve \(\chi_k\) for various \(k\).
Let \(K_t\) denote the complete graph on \(t\) vertices, \({\mathcal O}_t\) the edgeless graph on \(t\) vertices. Both graphs in \(\mathcal{G}_n\). The subscripts are omitted when the order is implicit from the text. Further we say a pair of edges are parallel if they are nonadjacent (in \(K_n\)).
The following two lemmas will be essential in our characterizations:
Lemma 1.1. [1, 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.
Note that if \(T\) is linear and bijective, then \(T\) preserves \(|E(G)|\) since every graph in \(\mathcal{G}_n\) has but a finite number of edges.
Lemma 1.2. Let \(T:\mathcal{G}_n\to\mathcal{G}_n\) be a linear operator. Then the following are equivalent:
1. \(T\) is injective;
2. \(T\) is surjective;
3. \(T\) is bijective.
Proof. This follows from the fact that \(\mathcal{G}_n\) is finite. ◻
In this section we shall use the facts that \(\chi_1(K_n)=n\) while, for any edge graph, \(E\), \(\chi_1(K_n\setminus E)=n-1\): suppose \(E\) is the edge joining vertex \(v\) to vertex \(u\); then, \(u\) and \(v\) can be labeled with the same label. If \(n=2\), the only linear operators on \(\mathcal{G}_n\) are the zero operator and vertex permutations. We thus assume in this section that \(n\geq 3\).
Lemma 2.1. Let \(T:\mathcal{G}_n\to\mathcal{G}_n\) be a linear operator that preserves \(\chi_1\). Then \(T\) is nonsingular.
Proof. Suppose \(T(X)=O\) for some graph \(X\). Then, since \(\mathcal{G}_n\) is an antinegative semiring whose addition is the union of the edge sets, there is some edge graph, \(E\), (actually any edge in \(X\)) such that \(T(E)=O\). Let \(F\) and \(G\) be edge graphs such that \(H=E\cup F\cup G\) is a three cycle. Then, \(\chi_1(H)=3\) while \(\chi_1(H\setminus E)=2\) since \(H\setminus E\) is a 2-star. But since \(T(E)=O\), \(T(H)=T(H\setminus E)\), a contradiction. Thus \(T\) is nonsingular. ◻
Note that \(T\) being nonsingular only means that the only graph mapped to the empty graph is the empty graph itself. Unlike linear maps over fields, it does not imply invertibility, that we must prove.
Lemma 2.2. Let \(T:\mathcal{G}_n\to\mathcal{G}_n\) be a linear operator that preserves \(\chi_1\). Then \(T\) maps edge graphs to edge graphs.
Proof. Suppose that \(T(E)\) has at least two edges where \(E\) is an edge graph. Let \(E=E_1, E_2, \dots E_{n\choose 2}\) be the edge graphs of \(K_n\). Then, since \(T(E_1)\) has at least two edges, there must be some edge, say \(F\) such that \(T(K_n\setminus F) =T(K_n)\), a contradiction since \(\chi_1(K_n)=n\) while \(\chi_1(K_n\setminus F)=n-1\). ◻
Lemma 2.3. Let \(T:\mathcal{G}_n\to\mathcal{G}_n\) be a linear operator that preserves \(\chi_1\). Then \(T\) is bijective.
Proof. By Lemma 1.2 we only need show that \(T\) is injective. Further, we show that \(T\) is injective on the set of edge graphs, and it follows that \(T\) is injective on all of \(\mathcal{G}_n\).
Suppose that \(T(E)=T(F)\) for two edge graphs \(E\) and \(F\). Then \(T(K_n\setminus F)=T(K_n)\). But \(\chi_1(K_n)=n\) while \(\chi_1(K_n\setminus F)=n-1\), contradicting that \(T\) preserves \(\chi_1\). Thus, \(T\) is injective and hence bijective on the set of edge graphs, and consequently on all of \(G_n\) ◻
Lemma 2.4. Let \(T:\mathcal{G}_n\to\mathcal{G}_n\) be a linear operator that preserves \(\chi_1\). Then \(T\) maps 2-stars to 2-stars..
Proof. For \(n=3\) the proof is trivial, there are no parallel pairs. Suppose \(n\geq 4\). Let \(E\cup F\) be a two star. Suppose \(T(E\cup F)\) is not a two star, then it is a pair of parallel (disjoint) edges. Let \(G\) be the edge graph such that \(E\cup F\cup G\) is a 3-cycle. Then, \(T(E\cup F\cup G)\) is 3 parallel edges, a two star plus a nonadjacent edge or a three path. Each of these graphs have chromatic number two, while the chromatic number of a three cycle is three, contradicting that \(T\) preserves \(\chi_1\). ◻
Theorem 2.5. Let \(T:\mathcal{G}_n\to\mathcal{G}_n\) be a linear operator that preserves \(\chi_1\). Then \(T\)is a vertex permutation.
Proof. By Lemma 2.3, \(T\) is bijective, by Lemma 2.4, \(T\) maps two stars to two stars, and by Lemma 1.1, \(T\) is a vertex permutation. ◻
In this section we use the fact that \(\chi_2(G)=1\) if and only if \(G\) is a graph consisting of disjoint edges, so that the maximum degree of any vertex is 1, \(\Delta(G)=1\). Further, if \(S\) is a star graph, only one vertex of degree larger than 1, then \(\chi_2(S)=2\), and if \(L\) is a graph containing a 3-cycle then \(\chi_2(L)\geq 3\).
Lemma 3.1. Let \(T:\mathcal{G}_n\to\mathcal{G}_n\) be a linear operator that preserves \(\chi_2\). Then \(T\) is nonsingular.
Proof. Suppose \(T(X)=O\) for some graph \(X\). Then, since \(\mathcal{G}_n\) is an antinegative semiring whose addition is the union of the edge sets, there is some edge graph, \(E\), (actually any edge in \(X\)) such that \(T(E)=O\). Let \(F\) be an edge graph such that \(E\cup F\) is a two edge path. Then \(\chi_2(F)=1\) and \(\chi_2(E\cup F)=2\). But, \(T(F)=T(E\cup F)\), contradicting that \(T\) preserves \(\chi_2\). ◻
Lemma 3.2. Let \(T:\mathcal{G}_n\to\mathcal{G}_n\) be a linear operator that preserves \(\chi_2\). Then \(T\) maps edge graphs to edge graphs.
Proof. If \(n=3\) and \(T\) maps an edge graph to a graph with more than one edge then it maps an edge graph to a 2-path, an impossibility since \(\chi_2\) of an edge graph is one and \(\chi_2\) of a 2-path is 2, or to \(K_3\), also impossible since \(\chi_2(K_3=3\).
Let \(n\geq 4\), and suppose that for edge graph \(E\), \(T(E)\) has at least two edges (\(|T(E)|\geq 2\)). Let \(E_1=E=(v_1,v_2)\), and for \(j= 2, \dots, \lfloor{\frac{n}{2}}\rfloor\) let \(E_j=(v_{2j-1},v_{2j})\), so that \(H=E_1\cup E_2\cup \dots E_{ \lfloor{\frac{n}{2}}\rfloor}\) is a graph of \(\lfloor{\frac{n}{2}}\rfloor\) disjoint edges and hence, \(\chi_2(H)=1\). Now, Since \(|T(E_1)|\geq 2\) there must be some \(j\) such that \(T(E_j)\) is a subgraph of \(T(E_1\cup E_2\cup \dots E_{j-1})\), in particular \(T(H)=T(H\setminus E_j)\). Let \(Q\) be the edge graph where \(Q=(v_{2(j-1)},v_{2j})\) and \(R\) the edge graph where \(R=(v_{2(j-1)},v_{2j-1})\). Then, \(H\cup Q \cup R\) is a graph containing a 3-cycle, \(Q\cup R\cup E_j\), and hence \(\chi_2(H\cup Q \cup R)\geq 3\). But, \((H\setminus E_j)\cup Q\cup R\) is a graph of disjoint edges and 3-star so that \(\Delta((H\setminus E_j)\cup Q\cup R)=2\) and consequently \(\chi_2((H\setminus E_j)\cup Q\cup R)=2\).
Since \(T(H\cup Q \cup R)=T((H\setminus E_j)\cup Q\cup R)\) we have arrived at a contradiction since \(T\) preserves \(\chi_2\). That is \(T\) maps edge graphs to edge graphs. ◻
Lemma 3.3. Let \(T:\mathcal{G}_n\to\mathcal{G}_n\) be a linear operator that preserves \(\chi_2\). Then \(T\) is bijective.
Proof. As in Lemma 2.3, by Lemma 1.2 we only need show that \(T\) is injective. Further, we show that \(T\) is injective on the set of edge graphs, and it follows that \(T\) is injective on all of \(\mathcal{G}_n\). Suppose that \(T(E)=T(F)\) for some edge graphs \(E\) and \(F\). By the above, we have that \(E\cup F\) is a pair of disjoint edges, since \(\chi_2(E)=1\) and \(\chi_2(P_2) =2\) for any two edge path. (Note here that we must now have \(n\geq 4\).) So \(E\cup F\) is contained in a complete graph on 4 vertices minus one edge. Let \(W\) be that complete graph on 4 vertices minus one edge containing edges \(E\) and \(F\). Then \(\chi_2(W)=4\) while \(\chi_2(W\setminus F)\leq3\). since \(W\setminus F\) is a triangle plus one edge or a four cycle. Since \(T(E)=T(F)\) we have that \(T(W)=T(W\setminus F)\) contradicting that \(T\) preserves \(\chi_2\). Thus, \(T\) is bijective on the set of edge graphs and consequently is bijective on \(\mathcal{G}_n\). ◻
Lemma 3.4. Let \(T:\mathcal{G}_n\to\mathcal{G}_n\) be a linear operator that preserves \(\chi_2\). Then \(T\) maps 2-stars to 2-stars..
Proof. Since \(T\) is bijective on the set of edge graphs (see above proof of Lemma 3.3) and the fact that for a two star \(S_2, \chi_2(S_2)=2\) while \(\chi_2\) is 1 for any pair of parallel edges, \(T\) maps two stars to two stars. ◻
Theorem 3.5. Let \(T:\mathcal{G}_n\to\mathcal{G}_n\) be a linear operator that preserves \(\chi_2\). Then \(T\)is a vertex permutation.
Proof. By Lemma 3.3, \(T\) is bijective, by Lemma 3.4, \(T\) maps two stars to two stars, and by Lemma 1.1, \(T\) is a vertex permutation. ◻
Let \(t\) be an integer, \(3\leq t \leq n-1\). Let \(T:\mathcal{G}_n\to\mathcal{G}_n\) be a linear operator that preserves \(\chi_t\). Since \(\mathcal{G}_n\) is finite, there is some positive integer \(d\) such that \(T^d\) is idempotent. Let \(Q=T^d\), so that \(Q^2=Q\) and \(Q\) is a linear preserver of \(\chi_t\).
Lemma 4.1. \(Q\) is nonsingular.
Proof. Suppose that \(Q(X)=O\) for some graph \(X\in\mathcal{G}_n\). Then, for \(E\) an edge of \(X, Q(E)=O\). Let \(P\) be a path of \(t\) edges that dominates \(E\). Then \(\chi_t(P)=2\) while \(\chi_t(P\setminus E)=1\). But \(Q(P)=Q(P\setminus E)\), contradicting that \(Q\) preserves \(\chi_t\). Thus, \(Q\) is nonsingular. ◻
Note that \(Q\) being nonsingular dois not imply invertibility as for vector spaces over fields, just that only \(O\) is mapped to \(O\).
Lemma 4.2. \(Q\) maps edge graphs to edge graphs.
Proof. Let \(E\) be an edge graph and suppose that \(Q(E)\) dominates more than one edge. Let \(F\) be an edge graph, \(F\neq E, \,\, F\in Q(E)\). Let \(F\) be the edge joining vertices \(u\) and \(v\) and \(E\) be the edge joining vertices \(a\) and \(b\), so that \(v\neq a,b\). Let \(H \cong K_t\) be a complete graph on \(t\) vertices with vertices \(a,b\) and \(u\) nonisolated, and vertex \(v\) isolated. Then \(\chi_t(H)=1\) and \(\chi_t(H\cup F)=2\). However \(Q(H) = Q(H\cup E)\) and \(F\in Q(E)\), so \(Q(H\cup F) = Q(F\cup E\cup H) = Q(F)\cup Q(E)\cup Q(H) =Q(F)\cup Q^2(E)\cup Q^2(H)= Q^2(E)\cup Q^2(H) =Q^2(H)\). That is, \(Q(F\cup H) = Q(H)\), a contradiction. Thus \(Q\) maps edge graphs to edge graphs. ◻
Lemma 4.3. \(Q\) is bijective.
Proof. Since \(\mathcal{G}_n\) is finite we only need show \(Q\) is injective, and since \(Q\) is linear we only need show \(Q\) is injective on the set of edge graphs. Suppose not. Let \(E\) anf \(F\) be edge graphs such that \(Q(E)=Q(F)\). Let \(P\) be a path on \(t\) edges dominating \(E\) and \(F\). Then \(\chi_t(P)=2\) while \(\chi_t(P\setminus F)=1\). But \(Q(P)=Q(P\setminus F)\), contradicting that \(Q\) preserves \(\chi_t\). Thus \(Q\) is injective on the set of edge graphs, hence injective on \(\mathcal{G}_n\), hence bijective on \(\mathcal{G}_n\). ◻
Theorem 4.4. Let \(T:\mathcal{G}_n\to\mathcal{G}_n\) be a linear operator preserving \(\chi_t\) for some \(t, 3\leq t\leq n-1\). Then \(T\) is bijective.
Proof. This follows directly from Lemma 4.3 since if \(T\) were not injective, neither would \(Q\) be injective. ◻
Lemma 4.5. If \(T:\mathcal{G}_n\to\mathcal{G}_n\) is a bijective linear operator mapping three edge paths to three edge paths, then \(T\) maps two edge paths to two edge paths (i.e. \(T\) preserves 2-stars).
Proof. First note that since \(T\) is bijective and the addition in \(\mathcal{G}_n\) is the union of the edge sets, the image of an edge graph is an edge graph.
Suppose that the image of a two edge path (2-star) is a pair of parallel edges. Say, \(E\) and \(F\) are edge graphs such that \(E\cup F\) is a two-edge path, and \(T(E\cup F)\) is a pair of parallel edges. Let \(G\) be an edge graph such that \(E\cup F\cup G\) is a three edge path. Then, since \(T\) preserves three edge paths, \(T(G)\) must join \(T(E\cup F)\) to form a three edge path. Let \(H\) be the edge graph such that \(E\cup F\cup G\cup H\) is a 4-cycle. Then \(E\cup F\cup G\), \(F\cup G\cup H\) and \(E\cup G\cup H\) are all three edge graphs, and hence, so must Their images be. That is \(T(F\cup G)\cup T(H)\) is a three edge path so \(T(H)\) must be incident with a vertex of \(T(F\cup G)\) of degree 1. But then \(T(E\cup G)\cup T(H)\)cannot be a three edge path, a contradiction. Thus \(T\) preserves 2-stars. ◻
Lemma 4.6. If \(T:\mathcal{G}_n\to\mathcal{G}_n\) is a bijective linear operator mapping four edge paths to four edge paths, then \(T\) maps two edge paths to two edge paths (i.e. \(T\) preserves 2-stars).
Proof. Suppose \(n=5\) or 6. Then if the image of a 2-star is not a two star, it is a pair of parallel edges. Say \(E\) anf \(F\) are edges forming a 2-star whose image is a pair of parallel edges. If \(G\) is the edge that makes a 3-cycle with \(E\) and \(F\) then, \(T(E\cup F\cup G)\) is
1. a three path,
2. a 2-path together with a disjoint edge, or
3. when \(n=6\), three mutually parallel edges.
In possibilities 1 and 2, since \(T\) is bijective, there is an edge graph \(H\) whose image is an edge that makes \(T(E\cup F\cup G)\cup T(H)\) a four edge path, but any edge added to \(E\cup F\cup G\) never dominates a four edge path, contradicting that \(T\) is bijective and maps four edge paths to four edge paths. Thus \(T\) preserves 2-stars.
In possibility 3, \(n=6\) and \(T(E\cup F\cup G)\) is a graph of three mutually parallel edges. Let \(E=v_1v_2, F=v_1v_3\) and \(G=v_2v_3\). Let \(H=v_3v_4\) and \(K=v_4v_5\). Then \(E\cup F\cup H\cup K\) and \(E\cup G\cup H\cup K\) are both four edge paths, but their images cannot both be four edge paths. This is a contradiction. Thus \(T\) preserves 2-stars.
Let \(n\geq 7\). There are exactly four edges that can be added to a two edge path and a non adjacent edge to create a four path. Since \(n\geq 7\), there are at least six edges that can be added to the three edge path to create a four edge path. Since \(T\) is bijective and maps four edge paths to four edge paths, \(T\) must map these six (or more) edges bijectively onto the four edges in the image that can be added to a two edge path and a non adjacent edge to create a four path. This impossibility establishes that \(T\) preserves three edge paths. By Lemma 4.5, \(T\) preserves two stars. ◻
Lemma 4.7. Let \(T:\mathcal{G}_n\to\mathcal{G}_n\) be a linear operator preserving \(\chi_t\) for some \(t, 3\leq t\leq n-1\). Then \(T\) maps 2-stars to 2-stars.
Proof. Since \(T\) is bijective, we will show that \(T\) maps a parallel pair of edge graphs to a parallel pair. Since \(\mathcal{G}_n\) is finite, it will follow that \(T\) maps 2-stars to 2-stars.
Let \(t\geq 5\). Let \(E\) and \(F\) be a parallel pair of edges, and suppose that \(T(E\cup F)\) is a 2-star. Let \(G\) be an edge graph such that \(T(E\cup F\cup G)\) is a 3-cycle. Let \(P\) be a graph of \(t-3\) edges such that \(P\cup E\cup F\cup G\) is a path of \(t\) edges. This is always possible for \(t\geq 5\). Then, \(\chi_t(P\cup E\cup F\cup G)=2\). Now a three cycle with \(t-3\) additional edges contains no path on \(t\) edges, so \(\chi_t(P\cup E\cup F\cup G)=1\), a contradiction. Thus parallel pairs are mapped to parallel pairs and 2-stars are mapped to 2-stars when \(t\geq 5\).
Let \(t=4\) Since \(T\) is bijective and preserves \(\chi_4\), \(T\) preserves four edge paths. By Lemma 4.6 \(T\) preserves two stars.
Let \(t=3\). Since \(T\) is bijective and preserves \(\chi_3\), \(T\) preserves three edge paths. By Lemma 4.5 \(T\) preserves two stars. ◻
Theorem 4.8. Let \(T:\mathcal{G}_n\to\mathcal{G}_n\) be a linear operator preserving \(\chi_t\) for some \(t, 3\leq t\leq n-1\). Then \(T\) is a vertex permutation.
Proof. By Theorem 4.4, \(T\) is bijective (and also preserves the number of edges in a graph). By Lemma 4.7, \(T\) preserves 2-stars. By Lemma 1.1, \(T\) is a vertex permutation. ◻