Fawwaz F. Hadiputra^a , Kiki A. Sugeng^a , Denny R. Silaban^a , Tita K. Maryati^b , Dalibor Froncek^c

^aDepartment of Mathematics, Faculty of Mathematics and Natural Sciences,

Universitas Indonesia, Depok - Indonesia.

^bDepartment of Mathematics Education, Faculty of Tarbiyah and Teacher Training (FITK),

UIN Syarif Hidayatullah Jakarta, Ciputat - Indonesia.

{fawwazfh, denny, kiki}@sci.ui.ac.id, tita.khalis@uinjkt.ac.id, dalibor@d.umn.edu

Let G(V, E) be a simple graph and f be a bijection f : V ∪ E → {1, 2, . . . , |V | + |E|} where f(V ) = {1, 2, . . . , |V |}. For a vertex x ∈ V , define its weight w(x) as the sum of labels of all edges incident with x and the vertex label itself. Then f is called a super vertex local antimagic total (SLAT) labeling if for every two adjacent vertices their weights are different. The super vertex local antimagic total chromatic number χslat(G) is the minimum number of colors taken over all colorings induced by super vertex local antimagic total labelings of G. We classify all trees T that have χslat(T) = 2, present a class of trees that have χslat(T) = 3, and show that for any positive integer n ≥ 2 there is a tree T with χslat(T) = n.

Keywords: super vertex local antimagic total labeling, super vertex local antimagic total chromatic number, tree, chromatic number

Mathematics Subject Classification : 05C05, 05C15, 05C78

DOI: 10.5614/ejgta.2021.9.2.19

Received: 19 October 2020, Revised: 31 May 2021, Accepted: 18 July 2021.

^cDepartment of Mathematics, University of Minnesota Duluth, USA.

1. Introduction

All graphs defined in this paper are simple and connected. Introduced by Arumugam et al. [1], a vertex local antimagic labeling is a bijective function f : E(G) −→ {1, 2, . . . , |E(G)|} such that w(u) 6= w(v) for any adjacent vertices u and v, where the weight w(x) of a vertex x ∈ V is the sum of labels of all edges incident with x. The minimum number of distinct weights needed for a graph G to have a vertex local antimagic labeling is denoted by χla(G). They conjectured that every connected graph other than K² is a vertex local antimagic graph, which was confirmed by Haslegrave using probabilistic method [4].

Putri et al. [7] introduced a new variant of vertex local antimagic labeling, called vertex local antimagic total labeling. A vertex local antimagic total labeling is a bijective map f : V (G) ∪ E(G) −→ {1, 2, . . . , |V (G)| + |E(G)|} such that w(u) 6= w(v) for any two adjacent vertices u and v. Here w(x) is the sum of labels of all edges incident with x and the label of x itself. The minimum of distinct weights so that a graph G has vertex local antimagic total labeling is denoted by χlat(G). The minimum number of distinct weights needed for a graph G to have a vertex local antimagic labeling is denoted by χla(G). Lau [5] adopts a result from Haslegrave [4] to show that every connected graph is a vertex local antimagic total graph. For more information on local antimagic or antimagic labelings, we refer the reader to Gallian's survey [3].

Furthermore, Slamin et al. [8] introduced a new variant of the labeling. A super vertex local antimagic total labeling is a bijective map f : V (G) ∪ E(G) −→ {1, 2, . . . , |V (G)| + |E(G)|} where f(V (G)) = {1, 2, . . . , |V (G)|} such that w(u) 6= w(v) for any two adjacent vertices u and v, where w(x) = f(x) + P xy∈E(G) f(xy).The minimum number of distinct weights needed for a graph G to have a super vertex local antimagic labeling is denoted by χslat(G). From the definition, we can perceive the super vertex local antimagic labeling as a vertex coloring of a graph with some additional conditions. An easy observation then follows.

Observation 1.1. For any graph G, χslat(G) ≥ χ(G).

We limit our current research to some classes of trees; in particular, stars Sn, paths Pn, caterpillars Sⁿ1,n2,...,n^k and shrubs Sˇ(n1, n2, . . . , nk). A shrub Sˇ(n1, n2, . . . , nk) is defined as a tree constructed from a star Sm, every leaf of which is adjacent to some number of isolated vertices (see [6]).

Slamin et al. [8] proved the following. If T is a tree on n ≥ 2 vertices with k leaves, then χslat(T) ≤ n − k + 1. For a star Sⁿ and a double star Sk,n−k, we have χslat(Sn+1) = 2 and χslat(Sk,n−k) = 3. In addition, if Pⁿ is a path, χslat(Pn) = 3 if n is odd and n ≥ 5, or 3 ≤ χslat(Pn) ≤ 4 if n is even and n ≥ 6.

In this paper, we characterize trees T with χslat(T) = 2, show existence of trees with χslat(T) = 3, and construct trees T that have χslat(T) = n for any positive integer n ≥ 2.

2. Characterization of Trees with χslat(T ) = 2

We start by determining the lower bound of χslat(T). The following Lemma 2.1 shows sufficient condition for vertices having different weights based on their degrees.

Lemma 2.1. Let T be a tree graph which has SLAT-labeling f and v1, v² ∈ V (T). If 2 deg(v1) + 1 ≤ deg(v2), then w(v1) < w(v2).

Proof. Let deg(v1) = d and |V | = n, so that deg(v2) ≥ 2d + 1 and |E| = n − 1. By assigning v¹ and edges incident with v¹ labels such that the weight of v¹ is as large as possible, we have

\[w(v_1) \le (d+1)|V| + d|E| - \sum_{i=1}^{d} (i-1)\] \[w(v_1) \le (d+1)n + d(n-1) - \frac{(d-1)d}{2}\] \[w(v_1) \le 2dn + n - \frac{d^2 + d}{2}.\]

Then, by assigning v² and edges incident with v² labels such that the weight of v² is as small as possible, we have

\[w(v_2) \ge (2d+1)|V| + \sum_{i=1}^{2d+1} (i+1)\] \[w(v_2) \ge (2d+1)n + \frac{(2d+1)(2d+2)}{2} + 1\] \[w(v_2) \ge 2dn + n + 2d^2 + 3d + 1.\]

It can be seen that w(v1) < w(v2).

The following special case where v¹ is a leaf will be useful.

Corollary 2.1. For an arbitrary tree, if v¹ is a leaf vertex and v² is a vertex with deg(v2) ≥ 3, then w(v1) 6= w(v2).

Based on [8], χslat(Sn) = 2. We will show that stars are the only trees with χslat(T) = 2. In our proof, we provide a labeling different from the one in [8].

Theorem 2.1. Suppose T is a tree graph, then χslat(T) = 2 if and only if T ∼= Sⁿ for n ∈ N.

Proof. Let T ∼= Sⁿ for n ∈ N, we will show that χslat(T) = 2. By the fact that χ(T) = 2 and Observation 1.1 we conclude that χslat(T) ≥ 2. To show χslat(T) ≤ 2, define f : V (T)∪E(T) −→ {1, 2, . . . , |V (T)| + |E(T)|} as follows:

\[f(c) = n + 1,\]
\(f(v_i) = i, 1 \le i \le n,\)
\(f(cv_i) = 2n + 2 - i, i \le i \le n.\)

From here, we get

\[w(v_i) = 2n + 2, 1 \le i \le n,\]
\(w(c) = \frac{3}{2}n^2 + \frac{5}{2}n + 1.\)

Therefore, χslat(T) ≤ 2. We conclude that if T ∼= Sn, then χslat(T) = 2. Now let χslat(T) = 2, we will show that T ∼= Sn.

Let the partition of V (T) be V1, V2. Without loss of generality, let x⁰ ∈ V¹ and P = x0, y1, x1, . . . be a diametrical path. Then x⁰ is of degree one. By Corollary 2.1, all vertices in V¹ are of degree at most two and therefore all vertices of V² belong to P. Denote by p the number of leaves in V¹ and by q the number of vertices of degree two. We want to show that q = 0.

Using this notation, we can see that P = x0, y1, x1, . . . , xq, yq+1 or P = x0, y1, x1, . . . , xq, yq+1, xq+1 and |V2| = q + 1. Therefore, we have

\[|V| = |V_1| + |V_2| = (p+q) + (q+1) = p + 2q + 1,\]

which yields

\[p = |V| - 2q - 1.\]

Denote by V i 1 the set of vertices of degree i in V1. Then we have |V 1 1 | = p and |V 2 1 | = q. Denote |V | = m.

We know that all vertices in V¹ have the same weight, call it w ∗ . We first look at the p vertices of degree one, observing that

\[\sum_{x_i \in V_1^1} w(x_i) = pw^*. {1}\]

We also know that

\[\sum_{x_{i} \in V_{1}^{1}} w(x_{i}) = \sum_{x_{i} \in V_{1}^{1}} f(x_{i}) + \sum_{x_{i} \in V_{1}^{1}, x_{i} y_{j} \in E} f(x_{i} y_{j})\] \[\leq \sum_{s=m-p+1}^{m} s + \sum_{t=2m-p}^{2m-1} t\] \[= \frac{(2m-p+1)p}{2} + \frac{(4m-p-1)p}{2}\] (2)

Combining (1) and (2), we obtain

\[pw^* = \sum_{x_i \in V_1^1} w(x_i) \le \frac{(2m - p + 1)p}{2} + \frac{(4m - p - 1)p}{2},\tag{3}\]

which yields

\[w^* \le \frac{(2m-p+1)}{2} + \frac{(4m-p-1)}{2} = 3m-p,\tag{4}\]

Now we look at the q vertices of degree two, observing that

\[\sum_{x_i \in V_2^1} w(x_i) = qw^*. \tag{5}\]

We also know that

\[\sum_{x_{i} \in V_{1}^{2}} w(x_{i}) = \sum_{x_{i} \in V_{1}^{2}} f(x_{i}) + \sum_{x_{i} \in V_{1}^{2}, x_{i} y_{j} \in E} f(x_{i} y_{j})\] \[\geq \sum_{s=1}^{q} s + \sum_{t=m+1}^{m+2q} t\] \[= \frac{(q+1)q}{2} + \frac{(2m+2q+1)(2q)}{2}\] (6)

Combining (5) and (6), we obtain

\[qw^* = \sum_{x_i \in V_1^2} w(x_i) \ge \frac{(q+1)q}{2} + \frac{(2m+2q+1)(2q)}{2},\tag{7}\]

which for q > 0 yields

\[w^* \ge \frac{q+1}{2} + (2m+2q+1) = 2m + \frac{5q+3}{2}.\] (8)

We noted above that

\[p = |V| - 2q - 1 = m - 2q - 1. (9)\]

Substituting (9) into (4), we have

\[w^* \le 3m - p = 3m - (m - 2q - 1) = 2m + 2q + 1. \tag{10}\]

Now comparing (8) and (10), we get

\[2m + \frac{5q+3}{2} \le w^* \le 2m + 2q + 1,\tag{11}\]

which is impossible for q > 0. Hence, q = 0. We already noticed that |V2| = q + 1 = 1, which implies that T must be the star Sp.

In Figure 1, we give an example of SLAT labeling on S8.

Figure 1: SLAT labeling on S8, χslat(S8) = 2.

Corollary 2.2. Suppose T is a non-trivial tree graph and Sⁿ is a star graph. If T is not isomorphic to Sn, then χslat(T) ≥ 3.

3. Existence of Trees with \(\chi_{slat}(T)=3\)

Slamin et al. in [8] investigated paths \(P_n\) and proved that \(\chi slat(T_n) = 3\) when n is odd, and \(3 \le \chi_{slat}(T_n) \le 4\) when n is even. In Theorem 3.1, we present a more straightforward proof.

Theorem 3.1. Let \(P_n\) be a path on n vertices, \(n \ge 4\). Then \(\chi_{slat}(P_n) = 3\) when n is odd or \(n \in \{4, 6, 8, 10\}\) and \(3 \le \chi_{slat}(P_n) \le 4\) when n is even and \(n \ge 12\).

Proof. Let \(V(P_n) = \{v_i | 1 \le i \le n\}\) and \(E(P_n) = \{v_i v_{i+1} | 1 \le i \le n-1\}\) with \(n \in \mathbb{N}\). According to Corollary 2.2, graphs that are not isomorphic to a star have \(\chi_{slat}(P_n) \ge 3\). To show the upper bound, the problem is divided into two cases, according to the parity of n.

Case 1. n is odd

Define \(f: V(P_n) \cup E(P_n) \to \{1, 2, 3, ..., |V| + |E|\}\) as follows

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

\[f(v_i v_{i+1}) = \begin{cases} 2n-1, & \text{if } i=1, \\ n+\frac{i-1}{2}, & \text{if } 3 \le i \le n-2, i \text{ is odd,} \\ \frac{3}{2}(n-1)+\frac{i}{2}, & \text{if } 2 \le i \le n-1, i \text{ is even.} \end{cases}\]

Then we have the weights as follows.

\[w(v_i) = \begin{cases} 2n, & \text{if } \in \{1, n\}, \\ \frac{7}{2}n - \frac{1}{2}, & \text{if } 3 \le i \le n - 2, i \text{ is odd}, \\ \frac{7}{2}n + \frac{3}{2}, & \text{if } 4 \le i \le n - 1, i \text{ is even.} \end{cases}\]

Therefore, \(\chi_{slat}(P_n) \leq 3\).

Case 2. n is even

Define \(f:V(P_n)\cup E(P_n)\to \{1,2,3,\ldots,|V|+|E|\}\) as follows.

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

\[f(v_i v_{i+1}) = \begin{cases} n + \frac{i}{2}, & \text{if } 2 \le i \le n-2, i \text{ is even,} \\ \frac{3}{2}n + \frac{i-1}{2}, & \text{if } 1 \le i \le n-1, i \text{ is odd.} \end{cases}\]

Then we have the weights as follows.

\[w(v_i) = \begin{cases} \frac{5}{2}n, & \text{if} \quad i = 1, \\ 3n - 2, & \text{if} \quad i = n, \\ \frac{7}{2}n, & \text{if} \quad 3 \le i \le n - 2, i \text{ is odd,} \\ \frac{7}{2}n - 2, & \text{if} \quad 2 \le i \le n - 1, i \text{ is even.} \end{cases}\]

We conclude that χslat(Pn) = 3 when n is odd or n{4, 6, 8, 10}, and 3 ≤ χslat(Pn) ≤ 4 when n is even and n ≥ 12.

In Figure 2 we present SLAT labelings of P4, P6, P8, P¹⁰ and also P⁷ as an example for n odd. The labeling is not unique. Here are some labelings for P6, P8, P10. First bracket is vertex labels, second edges, third weights. The labelings for P6, P8, and P¹⁰ were found by Branson [2].

\[P_6 \\ [5, 3, 4, 1, 2, 6][11, 9, 7, 8, 10][16, 23, 20, 16, 20, 16]\]

P8 [8, 4, 1, 6, 5, 3, 2, 7][14, 12, 13, 11, 10, 9, 15][22, 30, 26, 30, 26, 22, 26, 22] [8, 3, 4, 2, 5, 7, 1, 6][13, 14, 9, 10, 12, 11, 15][21, 30, 27, 21, 27, 30, 27, 21] [7, 1, 2, 4, 6, 3, 5, 8][15, 12, 13, 11, 10, 9, 14][22, 28, 27, 28, 27, 22, 28, 22] [5, 2, 7, 6, 8, 3, 4, 1][10, 15, 9, 12, 11, 13, 14][15, 27, 31, 27, 31, 27, 31, 15] [3, 1, 5, 4, 7, 8, 6, 2][12, 15, 10, 14, 9, 11, 13][15, 28, 30, 28, 30, 28, 30, 15] [4, 1, 7, 6, 5, 3, 8, 2][11, 15, 9, 12, 14, 10, 13][15, 27, 31, 27, 31, 27, 31, 15] [7, 2, 3, 6, 1, 5, 4, 8][15, 11, 13, 9, 12, 10, 14][22, 28, 27, 28, 22, 27, 28, 22] [6, 1, 3, 7, 2, 5, 4, 8][15, 12, 11, 10, 14, 9, 13][21, 28, 26, 28, 26, 28, 26, 21]

P¹⁰ [8, 1, 7, 3, 2, 5, 4, 9, 6, 10][19, 14, 15, 16, 18, 11, 12, 13, 17][27, 34, 36, 34, 36, 34, 27, 34, 36, 27] [9, 6, 4, 5, 3, 7, 2, 1, 8, 10][19, 15, 12, 11, 17, 16, 13, 14, 18][28, 40, 31, 28, 31, 40, 31, 28, 40, 28]

Figure 2: SLAT labeling on P7, P⁴ and P6.

Based on the labelings of the short even paths above, we state the following.

Conjecture. For any even n ≥ 4, χslat(Pn) = 3.

As a common generalization of caterpillars and shrubs, we introduce a new class of trees called shrubs. A shrub Sˆ(m, n, p) is defined by its vertex and edge set as follows.

\[V(\hat{S}(m, n, p)) = \{c, v_i, v_i^j, u_k | 1 \le i \le m, 1 \le j \le n, 1 \le k \le p\}\]
\[E(\hat{S}(m, n, p)) = \{cv_i, v_i v_i^j, cu_k | 1 \le i \le m, 1 \le j \le n, 1 \le k \le p\}\]

When p=0, then \(\hat{S}(m,n,p)\) is a regular shrub (all \(u_k\) vertices and \(cu_k\) edges are omitted). Else, if \(m\leq 2\), then \(\hat{S}(m,n,p)\) is a caterpillar. However, when m=0, n=0, or m+p=1, then \(\hat{S}(m,n,p)\) is a star. Since we already know that \(\chi_{slat}(T)=2\) for \(T\cong S_n\), the case of graph which is isomorphic to a star is omitted.

Theorem 3.2. Suppose \(\hat{S}(m, n, p)\) is a modified shrub. For positive m, n, non-negative p and \(m + p \neq 1\), \(\chi_{slat}(\hat{S}(m, n, p)) = 3\).

Proof. Let \(\hat{S}(m,n,p)=\{c,v_i,v_i^j,u_k|1\leq i\leq m,1\leq j\leq n,1\leq k\leq p\}\) and \(E(\hat{S}(m,n,p))=\{cv_i,v_iv_i^j,cu_k|1\leq i\leq m,1\leq j\leq n,1\leq k\leq p\}\). By Corollary 2.2, graphs other than stars have \(\chi_{slat}(\hat{S}(m,n,p))\geq 3\). To show the upper bound, the proof is divided into two cases.

Case 1. \(p + m \ge n + 1\)

The case is divided into three subcases, according to the parity of n and m.

Subcase 1.1. n is even

Define \(f: V \cup E \to \{1, 2, 3, ..., |V| + |E|\}\) as follows

\[f(u_k) = k, 1 \le k \le p,\]

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\] \[f(v_i) = mn + p + i, 1 \leq i \leq m,\] \[f(c) = m(n+1) + p + 1,\] \[f(c) = m(n+1) + p + 1,\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\] \[f(cv_i) = m(2n+2) + 2p - i + 2, 1 \leq i \leq m,\] \[f(cu_k) = m(2n+1) + 2p - k + 2, 1 \leq k \leq p.\]

When p = 0, then vertices \(v_k\) and edges \(cv_k\) are omitted.

We have

\[w(u_k) = w(v_i^j) = m(2n+1) + 2p + 2, 1 \le k \le p, 1 \le i \le m, 1 \le j \le n,\] \[w(v_i) = m(n(2n + \frac{9}{2}) - \frac{n(n+1)}{2} + 2) + p(n+3) + \frac{3n}{2} + 2, 1 \le i \le m,\] \[w(c) = m((2m+1)(n+1) + p(2n+3) + 2) + \frac{p(3p+5)}{2} - \frac{m(m+1)}{2} + 1.\]

It can be seen that these three weights are different.

Subcase 1.2. Both n and m are odd

Define \(f: V \cup E \rightarrow \{1, 2, 3, \dots, |V| + |E|\}\) as follows

\[f(u_k) = k, 1 \le k \le p,\] \[f(v_i^j) = \begin{cases} m(j-1) + p + i, & \text{if} \quad 1 \le i \le m, 1 \le j \le n, j \text{ is odd,} \\ mj - i + p + 1, & \text{if} \quad 1 \le i \le m, 1 \le j \le n, j \text{ is even.} \end{cases}\] \[f(v_i) = \begin{cases} mn + p + \frac{m+1}{2} - i + 1, & \text{if} \quad 1 \le i \le \frac{m+1}{2}, \\ m(n+1) + p + \frac{m+1}{2} - i + 1, & \text{if} \quad \frac{m+3}{2} \le i \le m. \end{cases}\] \[f(c) = m(n+1) + p + 1,\] \[f(v_i v_i^j) = \begin{cases} m(2n - j + 1) + p + i + 1, & \text{if} \quad 1 \le i \le m, 1 \le j \le n, j \text{ is even,} \\ m(2n - j + 2) + p - i + 2, & \text{if} \quad 1 \le i \le m, 1 \le j \le n, j \text{ is odd.} \end{cases}\] \[f(cv_i) = \begin{cases} m(2n+1) + 2p + 2i, & \text{if} \quad 1 \le i \le \frac{m+1}{2}, \\ 2mn + 2p + 2i, & \text{if} \quad \frac{m+3}{2} \le i \le m. \end{cases}\] \[f(cu_k) = m(2n+1) + 2p - k + 2, 1 \le k \le p.\]

When p = 0, then vertices \(v_k\) and edges \(cv_k\) are omitted.

We have

\[w(u_k) = w(v_i^j) = m(2n+1) + 2p + 2, 1 \le k \le p, 1 \le i \le m, 1 \le j \le n,\] \[w(v_i) = m(2n(n+2) + (1-n)\frac{n+1}{2} + 1) + p(n+3) + \frac{m+3n}{2} + 2, 1 \le i \le m,\] \[w(c) = m((2m+1)(n+1) + p(2n+3) + 2) + \frac{p(3p+5)}{2} - \frac{m(m+1)}{2} + 1.\]

It can be seen that these three weights are different.

Subcase 1.3. n is odd and m is even

Define \(f: V \cup E \rightarrow \{1, 2, 3, \dots, |V| + |E|\}\) as follows

\[f(u_k) = k, 1 \le k \le p,\] \[f(v_i^j) = \begin{cases} m(j-1) + p + i, & \text{if} \quad 1 \le i \le m, 1 \le j \le n, j \text{ is odd,} \\ mj - i + p + 1, & \text{if} \quad 1 \le i \le m, 1 \le j \le n, j \text{ is even.} \end{cases}\] \[f(v_i) = \begin{cases} mn + p + \frac{i+1}{2} + 1, & \text{if} \quad 1 \le i \le m, i \text{ is odd,} \\ mn + p + \frac{m+i}{2} + 1, & \text{if} \quad 1 \le i \le m, i \text{ is even.} \end{cases}\] \[f(c) = mn + p + \frac{m}{2} + 1,\] \[f(v_i v_i^j) = \begin{cases} m(2n - j + 1) + p + i + 1, & \text{if} \quad 1 \le i \le m, 1 \le j \le n, j \text{ is even,} \\ m(2n - j + 2) + p - i + 2, & \text{if} \quad 1 \le i \le m, 1 \le j \le n, j \text{ is odd.} \end{cases}\]

Chromatic number of SLAT labelings of graphs | Hadiputra et al.

\[f(cv_i) = \begin{cases} m(2n+1) + 2p + \frac{i}{2} + 1, & \text{if } 1 \le i \le m, i \text{ is even,} \\ m(2n+1) + 2p + \frac{m+i+1}{2} + 1, & \text{if } 1 \le i \le m, i \text{ is odd.} \end{cases}\]\[f(cu_k) = m(2n+1) + 2p - k + 2, 1 \le k \le p.\]

When p = 0, then vertices \(v_k\) and edges \(cv_k\) are omitted.

We have

\[w(u_k) = w(v_i^j) = m(2n+1) + 2p + 2, 1 \le k \le p, 1 \le i \le m, 1 \le j \le n,\] \[w(v_i) = m(2n(n+2) + (1-n)\frac{n+1}{2} + 1) + p(n+3) + \frac{m+3n+1}{2} + 2, 1 \le i \le m,\] \[w(c) = m((2m+1)(n+1) + p(2n+3) + \frac{3}{2}) + \frac{p(3p+5)}{2} - \frac{m(m+1)}{2} + 1.\]

It can be seen that these three weights are different.

Case 2. p + m < n + 1

The case is divided into three subcases according to the parity of n and m.

Subcase 2.1. n is even

Define \(f: V \cup E \to \{1, 2, 3, ..., |V| + |E|\}\) as follows.

\[f(v_i^j) = \begin{cases} m(j-1) + i, & \text{if } 1 \le i \le m, 1 \le j \le n, j \text{ is odd,} \\ mj - i + 1, & \text{if } 1 \le i \le m, 1 \le j \le n, j \text{ is even.} \end{cases}\] \[f(v_i^j) = mn + p + i + 1, 1 \le i \le m,\] \[f(c) = mn + p + 1,\] \[f(c) = mn + p + 1,\] \[f(v_i v_i^j) = \begin{cases} m(2n - j + 2) + 2p + i + 1, & \text{if } 1 \le i \le m, 1 \le j \le n, j \text{ is even,} \\ m(2n - j + 3) + 2p - i + 2, & \text{if } 1 \le i \le m, 1 \le j \le n, j \text{ is odd.} \end{cases}\] \[f(cv_i) = m(n+2) + p - i + 2, 1 \le i \le m,\] \[f(cu_k) = m(n+2) + 2p - k + 2, 1 \le k \le p.\]

When p = 0, then vertices \(v_k\) and edges \(cv_k\) are omitted.

We have

\[w(u_k) = w(v_i^j) = m(2n+2) + 2p + 2, 1 \le k \le p, 1 \le i \le m, 1 \le j \le n,\] \[w(v_i) = m(n(2n + \frac{9}{2}) - \frac{n(n+1)}{2} + 2) + 2p(n+1) + \frac{3n}{2} + 3, 1 \le i \le m,\] \[w(c) = m((m+2)(n+2) + p) + \frac{p(3p+5)}{2} - \frac{m(m+1)}{2} + 1.\]

It can be seen that these three weights are different.

Subcase 2.2. Both n and m are odd

Define \(f: V \cup E \rightarrow \{1, 2, 3, \dots, |V| + |E|\}\) as follows.

\[f(u_k) = mn + k, 1 \le k \le p,\] \[f(v_i^j) = \begin{cases} m(j-1) + i, & \text{if} \quad 1 \le i \le m, 1 \le j \le n, j \text{ is odd,} \\ mj - i + 1, & \text{if} \quad 1 \le i \le m, 1 \le j \le n, j \text{ is even.} \end{cases}\] \[f(v_i) = \begin{cases} mn + p + \frac{m+1}{2} - i + 2, & \text{if} \quad 1 \le i \le \frac{m+1}{2}, \\ m(n+1) + p + \frac{m+1}{2} - i + 2, & \text{if} \quad \frac{m+3}{2} \le i \le m. \end{cases}\] \[f(c) = mn + p + 1,\] \[f(c) = mn + p + 1,\] \[f(v_i v_i^j) = \begin{cases} m(2n - j + 2) + 2p + i + 1, & \text{if} \quad 1 \le i \le m, 1 \le j \le n, j \text{ is even,} \\ m(2n - j + 3) + 2p - i + 2, & \text{if} \quad 1 \le i \le m, 1 \le j \le n, j \text{ is odd.} \end{cases}\] \[f(cv_i) = \begin{cases} m(n+1) + p + 2i, & \text{if} \quad 1 \le i \le \frac{m+1}{2}, \\ mn + p + 2i, & \text{if} \quad \frac{m+3}{2} \le i \le m. \end{cases}\] \[f(cu_k) = m(n+2) + 2p - k + 2, 1 \le k \le p.\]

When p = 0, then vertices \(v_k\) and edges \(cv_k\) are omitted.

We have

\[w(u_k) = w(v_i^j) = m(2n+2) + 2p + 2, 1 \le k \le p, 1 \le i \le m, 1 \le j \le n,\] \[w(v_i) = m(2n(n+2) + (1-n)\frac{n+1}{2} + 1) + 2p(n+1) + \frac{m+3n}{2} + 3, 1 \le i \le m,\] \[w(c) = m((m+1)(n+\frac{3}{2}) + p(n+3)) + \frac{p(3p+5)}{2} + 1.\]

It can be seen that these three weights are different.

Subcase 2.3. n is odd and m is even

Define \(f: V \cup E \to \{1, 2, 3, ..., |V| + |E|\}\) as follows.

\[f(u_k) = mn + k, 1 \le k \le p,\] \[f(v_i^j) = \begin{cases} m(j-1) + i, & \text{if} \quad 1 \le i \le m, 1 \le j \le n, j \text{ is odd,} \\ mj - i + 1, & \text{if} \quad 1 \le i \le m, 1 \le j \le n, j \text{ is even.} \end{cases}\] \[f(v_i) = \begin{cases} mn + p + \frac{i+1}{2}, & \text{if} \quad 1 \le i \le m, i \text{ is odd,} \\ mn + p + \frac{m+i}{2} + 1, & \text{if} \quad 1 \le i \le m, i \text{ is even.} \end{cases}\] \[f(c) = mn + p + \frac{m}{2} + 1,\]

Chromatic number of SLAT labelings of graphs | Hadiputra et al.

\[f(v_iv_i^j) = \begin{cases} m(2n-j+2) + 2p+i+1, & \text{if} \quad 1 \leq i \leq m, 1 \leq j \leq n, j \text{ is even,} \\ m(2n-j+3) + 2p-i+2, & \text{if} \quad 1 \leq i \leq m, 1 \leq j \leq n, j \text{ is odd.} \end{cases}\] \[f(cv_i) = \begin{cases} m(n+1) + p + \frac{i}{2} + 1, & \text{if} \quad 1 \leq i \leq m, i \text{ is even,} \\ m(n+1) + p + \frac{m+i+1}{2} + 1, & \text{if} \quad 1 \leq i \leq m, i \text{ is odd.} \end{cases}\] \[f(cu_k) = m(2n+1) + 2p - k + 2, 1 \leq k \leq p.\]

When p = 0, then vertices \(v_k\) and edges \(cv_k\) are omitted.

We have

\[w(u_k) = w(v_i^j) = m(2n+2) + 2p + 2, 1 \le k \le p, 1 \le i \le m, 1 \le j \le n,\] \[w(v_i) = m(2n(n+2) + (1-n)\frac{n+1}{2} + 1) + 2p(n+1) + \frac{m+3n+1}{2} + 2, 1 \le i \le m,\] \[w(c) = m((m+1)(n+\frac{3}{2}) + p(2n+3) + \frac{1}{2}) + \frac{p(3p+5)}{2} + 1.\]

It can be seen that these three weights are different.

From the above cases, we can conclude that \(\chi_{slat}(\check{S}'(m,n,p)) \leq 3\). Hence, \(\chi_{slat}(\check{S}'(m,n,p)) = 3\).

In Figure 3, we have examples of two cases in the preceding theorem.

Figure 3: SLAT labeling on T, \(\chi_{slat}(T) = 3\).

Corollary 3.1. If a tree T is isomorphic to a regular shrub \(\check{S}(n, n, n, \dots, n)\) or a caterpillar \(S_{n_1, n_2}\) or \(S_{n_1, n_2, n_1}\), then \(\chi_{slat}(T) = 3\).

4. Construction of Trees T with \(\chi_{slat}(T)=n\) for any \(n\in\mathbb{N}\)

Motivated by the fact that for any tree (an in fact for any bipartite graph) the regular chromatic number \(\chi(T)=2\), it is natural to ask whether there exists \(k\in\mathbb{N}\) such that for every tree T, \(\chi_{slat}(T)\leq k\). In the following theorem we show that no such bound exists.

Theorem 4.1. For every n ≥ 2, there exists a tree T such that χslat(T) = n.

Proof. The assertion for n = 2 follows from Theorem 2.1 and for n = 3 from Theorem 3.1. Therefore, we only construct examples fro n ≥ 4.

We construct a tree T starting with the path Pn+1. For every i = 2, 3, . . . , n we define tⁱ = i 2 + 1 and join vertex vⁱ to 2 ^ti − 3 isolated vertices. From this construction, we obtain deg(vi) = 2^ti − 1, for 2 ≤ i ≤ n.

First, we need to show that χslat(T) ≥ n. According to the definition of SLAT-labeling, adjacent vertices must have different weights, therefore w(vi) 6= w(vi+1) for 1 ≤ i ≤ n.

By the graph construction, for any 1 ≤ i, j ≤ n such that j ≥ i + 2 the vertices vⁱ , v^j are non-adjacent and satisfy the condition 2 deg(vi) + 1 ≤ deg(v^j ). It then follows from Lemma 2.1 that w(vi) 6= w(v^j ). In addition, it follows from Corollary 2.1 that the weights of vertices of degree at least three are all greater than the weights of all leaves. Thus, the graph needs at least n distinct weights, which means χslat(T) ≥ n.

To show χslat(T) ≤ n, we define a labeling f as follows. For i = 2, 3, . . . , n and l = 1, 2, . . . , tⁱ we denote by ei,l the pendant edges incident with vertex vⁱ and by vi,l the leaf incident with ei,l. First we label edge v1v² with label |V | + 1. Then we label the remaining pendant edges starting with the lowest available edge label |V |+ 2 in lexicographic order; that is, f(ei,l) < f(ei,s) for any 1 ≤ l < s ≤ tⁱ and f(ei,l) < f(i, s) for any 2 ≤ i < j ≤ n and any l and s. Next, label the leaf incident with an edge ei,l (or v1v2) so that the sum of the edge and vertex label equals 2|V | −n+ 2.

Then, label the vertices v2, v3, . . . , vⁿ starting from f(v2) = |V |−n+2 consecutively in increasing order. Finally, label the remaining edges starting from f(v2v3) = 2|V | − n + 2consecutively in increasing order. From this labeling, we have w(vi,l) = 2|V | − n + 2 for every leaf vertex vi,l, while 2|V | − n + 2 < w(vi) ≤ w(v^j ) for 2 ≤ i < j ≤ n. Hence, χslat(T) ≤ n.

We can conclude that χslat(T) = n.

5. Open Problems

To conclude, we state some obvious open problems.

• 1. Characterize trees with χslat(T) = 3.
• 2. Determine χslat(G) for other natural classes of graphs.

Acknowledgement

This research is funded by PUTI 2020 Research Grant, Universitas Indonesia No. NKB-779/UN2.RST/HKP.05.00/2020.

References

• [1] S. Arumugam, K. Premalatha, M. Baca, and A. Semani ˇ cov ˇ a-Fe ´ nov ˇ cˇ´ıkova, Local antimagic ´ vertex coloring of a graph, Graphs and Combinatorics 33 (2017), 275–285.
• [2] L. Branson, personal communication.

• [3] J.A. Gallian, A dynamic survey of graph labeling, The Electronic Journal of Combinatorics DS#6 (2019).
• [4] J. Haslegrave, Proof of a local antimagic conjecture, Discrete Mathematics and Theoretical Computer Science 20 (1) (2018), #18.
• [5] G. Lau, Every graph is local antimagic total, arXiv:1906.10332v2 (2019).
• [6] T.K. Maryati, E.T. Baskoro, and A.N.M. Salman, Ph-supermagic labelings of some trees, Journal of Combinatorial Mathematics and Combinatorial Computing 65 (2008), 197–204.
• [7] D.F. Putri, Dafik, I.H. Agustin, and R. Alfarisi, On the local vertex antimagic total coloring of some families tree, J. Phys.: Conf. Ser. 1008 (2018), 012035.
• [8] Slamin, N.A. Adiwijaya, M.A. Hasan, Dafik, and K. Wijaya, Local super antimagic total labeling for vertex coloring of graphs, Symmetry 12 (11) (2020), 1843.