Local Antimagic Chromatic Number for Copies of Graphs

Abstract

An edge labeling of a graph $G=(V,E)$ using every label from the set $\{1,2,\cdots ,|E(G)\left|\right\}$ exactly once is a local antimagic labeling if the vertex-weights are distinct for every pair of neighboring vertices, where a vertex-weight is the sum of labels of all edges incident with that vertex. Any local antimagic labeling induces a proper vertex coloring of G where the color of a vertex is its vertex-weight. This naturally leads to the concept of a local antimagic chromatic number. The local antimagic chromatic number is defined to be the minimum number of colors taken over all colorings of G induced by local antimagic labelings of G. In this paper, we estimate the bounds of the local antimagic chromatic number for disjoint union of multiple copies of a graph.

1. Introduction

In this paper, we will consider only finite graphs without loops or multiple edges. For graph theoretic terminology we refer to the book by Chartrand and Lesniak [1].

An antimagic labeling of a graph $G=(V,E)$ is a bijection f from the set of edges of G to the integers $\{1,2,\cdots ,|E(G)\left|\right\}$ such that all vertex-weights are pairwise distinct, where a vertex-weight is the sum of labels of all edges incident with that vertex, i.e., for the vertex $u\in V(G)$ the weight $wt(u)={\displaystyle \sum _{uv\in E(G)}}f(uv)$. A graph is called antimagic if it admits an antimagic labeling.

The concept of antimagic labeling was introduced by Hartsfield and Ringel [2] who conjectured that every simple connected graph, other than $K_2$, is antimagic. This conjecture is still open although for some special classes of graphs it was proved, see for instance [3,4,5,6,7,8]. Alon et al. [9] proved that large dense graphs are antimagic. Hefetz et al. [10] proved that any graph on $p^k$ vertices that admits a $C_p$-factor, where p is an odd prime and k is a positive integer, is antimagic. Perhaps the most remarkable result to date is the proof for regular graphs of odd degree given by Cranston et al. in [11], which was subsequently adapted to regular graphs of even degree by Bércz et al. in [12] and by Chang et al. in [13].

Recently, two groups of authors in [14,15] independently introduced a local antimagic labeling as local version of the Hartsfield and Ringel’s concept of antimagic labeling. An edge labeling using every label from the set $\{1,2,\cdots ,|E(G)\left|\right\}$ exactly once is a local antimagic labeling if the vertex-weights $wt(u)$ and $wt(v)$ are distinct for every pair of neighboring vertices u, v.

In [14] authors conjectured that any connected graph other than $K_2$ admits a local antimagic labeling. Bensmail et al. [15] propose the slightly stronger form of the previous conjecture that every graph without component isomorphic to $K_2$ has a local antimagic labeling. This conjecture was proved by Haslegrave [16] using the probabilistic method.

Any local antimagic labeling induces a proper vertex coloring of G where the vertex-weight $wt(u)$ is the color of u. This naturally leads to the concept of a local antimagic chromatic number introduced in [14]. The local antimagic chromatic number ${\chi }_{la}(G)$ is defined to be the minimum number of colors taken over all colorings of G induced by local antimagic labelings of G.

For any graph G, ${\chi }_{la}(G)\ge \chi (G)$, where $\chi (G)$ is the chromatic number of G as the minimum number of colors needed to produce a proper coloring of G. In [14] is investigated the local antimagic chromatic number for paths, cycles, friendship graphs, wheels and complete bipartite graphs. Moreover, there is proved that for any tree T with l leaves ${\chi }_{la}(T)\ge l+1$.

In this paper, we investigate the local antimagic chromatic number for disjoint union of multiple copies of a graph G, denoted by $mG$, $m\ge 1$, and we present some estimations of this parameter.

Please note that G does not have to be necessarily connected. By the symbol $x_i$ we denote the element (vertex or edge) corresponding to the element (vertex or edge) x in the ith copy of G in $mG$, $i=1,2,\cdots ,m$.

2. Graphs with Vertices of Even Degrees

A graph G is called equally 2-edge colorable if it is possible to color its edges with two colors $c_1$, $c_2$ such that for every vertex $v\in V(G)$ the number of edges incident to the vertex v colored with color $c_1$ is the same as the number of edges incident to the vertex v colored with color $c_2$. This means that for any vertex $v\in V(G)$ is $n^1(v)=n^2(v)$, where $n^i(v)$ denotes the number of edges incident to the vertex v and colored with color $c_i$, $i=1,2$. Trivially, if a graph G is equally 2-edge colorable then all vertices in G have even degrees.

Consider that G is an even regular graph. Then there exists an Euler circle in G. If we alternatively color the edges in the Euler circle with colors $c_1$ and $c_2$ we obtain that either for every vertex v in G holds $n^1(v)=n^2(v)$, or there exists exactly one vertex in G, say w, such that $n^1(w)=n^2(w)+2$.

Consider a 2-edge coloring c of a graph G. Let $c(G)$ denote the number of vertices in G such that $n_c^1(v)\ne n_c^2(v)$ under the labeling c. In this case we say that c is a $c(G)$-equally 2-edge coloring of G.

Let c be any 2-edge coloring of G. Let f be any bijective mapping in G, $f:E(G)\to \{1,2,\cdots ,|E(G)\left|\right\}$. We define an edge labeling g of $mG$, $m\ge 1$ in the following way

$$\begin{array}{c}\hfill g(e_i)=\left\{\begin{array}{cc}m(f(e)-1)+i,\hfill & \mathrm{if}c(e)=c_1\mathrm{and}i=1,2,\cdots ,m,\hfill \\ mf(e)+1-i,\hfill & \mathrm{if}c(e)=c_2\mathrm{and}i=1,2,\cdots ,m.\hfill \end{array}\right.\end{array}$$

If an edge in G is labeled with the number t, $1\le t\le |E(G)|$, then the corresponding edges in $mG$ are labeled with numbers from the set $\{m(t-1)+1,m(t-1)+2,\cdots ,mt\}$. Thus we immediately obtain that the labeling g is a bijective mapping that assigns numbers $1,2,\cdots ,m|E(G)|$ to the edges of $mG$.

Moreover, for the weight of the vertex $v_i$, $i=1,2,\cdots ,m$, in $mG$ under the labeling g we obtain the following

$$\begin{array}{cc}\hfill w{t}_g(v_i)& ={\displaystyle \sum _{uv\in E(G)}}g(u_i{v}_i)={\displaystyle \sum _{\begin{array}{c}uv\in E(G):c(uv)=c_1\end{array}}}g(u_i{v}_i)+{\displaystyle \sum _{\begin{array}{c}uv\in E(G):c(uv)=c_2\end{array}}}g(u_i{v}_i)\hfill \\ & ={\displaystyle \sum _{\begin{array}{c}uv\in E(G):c(uv)=c_1\end{array}}}\left(m(f(uv)-1)+i\right)+{\displaystyle \sum _{\begin{array}{c}uv\in E(G):c(uv)=c_2\end{array}}}\left(mf(uv)+1-i\right)\hfill \\ & =m{\displaystyle \sum _{\begin{array}{c}uv\in E(G):c(uv)=c_1\end{array}}}f(uv)+(i-m)n_c^1(v)\hfill \\ & \hspace{1em}+m{\displaystyle \sum _{\begin{array}{c}uv\in E(G):c(uv)=c_2\end{array}}}f(uv)+(1-i)n_c^2(v)\hfill \\ & =m{\displaystyle \sum _{uv\in E(G)}}f(uv)+(i-m)n_c^1(v)+(1-i)n_c^2(v)\hfill \\ & =m·w{t}_f(v)+(i-m)n_c^1(v)+(1-i)n_c^2(v).\hfill \end{array}$$

Thus, for every vertex $v\in V(G)$ such that $n_c^1(v)=n_c^2(v)=\mathrm{deg}(v)/2$ we obtain

$$\begin{array}{c}\hfill w{t}_g(v_i)=m·w{t}_f(v)+\frac{(1-m)\mathrm{deg}(v)}{2}\end{array}$$

(1)

for $i=1,2,\cdots ,m$. This means that the corresponding vertices in different copies have the same weights. Summarizing the previous we obtain the following lemma that will be used later.

Lemma 1.

Let G be a graph and let c be a 2-edge coloring of G and let f, $f:E(G)\to \{1,2,\cdots ,|E(G)\left|\right\}$, be a bijection. Let m, $m\ge 1$, be a positive integer. Then there exists an edge labeling g of $mG$ such that the weights of vertices $v_i$, $i=1,2,\cdots ,m$, corresponding to the vertex $v\in V(G)$ satisfying $n_c^1(v)=n_c^2(v)=\mathrm{deg}(v)/2$ will be the same.

Immediately from the previous result we obtain the following theorem for equally 2-edge colorable graphs.

Theorem 1.

Let m be a positive integer. Let G be an equally 2-edge colorable graph and let f be a local vertex antimagic edge labeling of G that uses ${\chi }_{la}(G)$ colors. Let for every edge $uv\in E(G)$ be

$$mw{t}_f(v)+\frac{(1-m)\mathrm{deg}(v)}{2}\ne mw{t}_f(u)+\frac{(1-m)\mathrm{deg}(u)}{2}.$$

Then

$${\chi }_{la}(mG)\le {\chi }_{la}(G).$$

Proof. 

Let f be a local vertex antimagic edge labeling of G that uses ${\chi }_{la}(G)$ colors. Let c be an equally 2-edge coloring of G. This means that for every vertex $v\in V(G)$ is $n^1(v)=n^2(v)=\mathrm{deg}(v)/2$.

According to Lemma 1 and Equality (1) we obtain that there exists a labeling g of $mG$, $m\ge 1$, such that for every $v\in V(G)$ and every $i=1,2,\cdots ,m$ holds $w{t}_g(v_i)=m·w{t}_f(v)+(1-m)\mathrm{deg}(v)/2$. Thus, g is such labeling that the corresponding vertices in different copies have the same weights. If for all adjacent vertices $u,v\in V(G)$ holds

$$\begin{array}{c}\hfill mw{t}_f(v)+\frac{(1-m)\mathrm{deg}(v)}{2}\ne mw{t}_f(u)+\frac{(1-m)\mathrm{deg}(u)}{2}\end{array}$$

(2)

then also all adjacent vertices in $mG$ have distinct weights.

Moreover, ${\chi }_{la}(mG)\le {\chi }_{la}(G)$. This concludes the proof. □

Note, if G is a regular graph then the condition (2) trivially holds. Results in the next two theorems are based on the Petersen Theorem.

Proposition 1. (Petersen Theorem)

Let G be a $2r$-regular graph. Then there exists a 2-factor in G.

Notice that after removing edges of the 2-factor guaranteed by Petersen Theorem we have again an even regular graph. Thus, by induction, an even regular graph has a 2-factorization.

Theorem 2.

Let G be a $4r$-regular graph, $r\ge 1$. Then for every positive integer m

$${\chi }_{la}(mG)\le {\chi }_{la}(G).$$

Proof. 

Let G be a $4r$-regular graph. According to Petersen Theorem G is decomposable into 2-factors $F_1,F_2,\cdots ,F_{2r}$. Consider an edge coloring c of G defined such that

$$\begin{array}{cc}\hfill c(e)=& \left\{\begin{array}{cc}{c}_1,\hfill & \mathrm{if}e\in E(F_j),j=1,2,\cdots ,r,\hfill \\ c_2,\hfill & \mathrm{if}e\in E(F_j),j=r+1,r+2,\cdots ,2r.\hfill \end{array}\right.\hfill \end{array}$$

Evidently, c is an equally 2-edge coloring of G. Thus, immediately according to Theorem 1 we obtain the desired result. □

Theorem 3.

Let G be a $(4r+2)$-regular graph, $r\ge 0$, containing a 2-factor consisting only from even cycles. Then for every positive integer m

$${\chi }_{la}(mG)\le {\chi }_{la}(G).$$

Proof. 

Let G be a $(4r+2)$-regular graph containing a 2-factor consisting only from even cycles. Denote this 2-factor by $F_1$. Let us denote the edges in component $F_1$ by the symbols $e_1,e_2,\cdots ,e_{\left|VG\right|}$ arbitrarily in such a way that all cycles in $F_1$ are of the form $e_s{e}_{s+1}{e}_{s+2}\cdots e_{s+t}$, where $s,t$ are odd integers. As all cycles in $F_1$ are even, evidently every vertex in G is incident with an edge in $F_1$ with an even and also with an odd index.

According to Petersen Theorem the graph $G-F_1$ is decomposable into 2-factors $F_2,F_3,\cdots ,$$F_{2r+1}$. Consider an edge coloring c of G defined such that

$$\begin{array}{cc}\hfill c(e)=& \left\{\begin{array}{cc}{c}_1,\hfill & \mathrm{if}e\in E(F_1),e=e_{2i-1},i=1,2,\cdots ,\frac{|V(G)|}{2},\hfill \\ \hfill & \mathrm{or}\mathrm{if}e\in E(F_j),j=2,3,\cdots ,r+1,\hfill \\ c_2,\hfill & \mathrm{if}e\in E(F_1),e=e_{2i},i=1,2,\cdots ,\frac{|V(G)|}{2},\hfill \\ \hfill & \mathrm{or}\mathrm{if}e\in E(F_j),j=r+2,r+3,\cdots ,2r+1.\hfill \end{array}\right.\hfill \end{array}$$

It is easy to see that for every vertex $v\in V(G)$ holds

$$n^1(v)=n^2(v)=2r+1.$$

This means that c is an equally 2-edge coloring of G. By Theorem 1 we obtain that ${\chi }_{la}(mG)\le {\chi }_{la}(G)$. □

Corollary 1.

Let n, m be positive integers, $n\ge 2$, $m\ge 1$. Then

$${\chi }_{la}(m{C}_{2n})=3.$$

Proof. 

In [14] it was proved that ${\chi }_{la}(C_k)=3$ for every $k\ge 3$. According to Theorem 3 we obtain that if $k=2n$ then for every positive integer m holds ${\chi }_{la}(m{C}_{2n})\le 3$.

Now suppose there exists a local antimagic labeling f that induces a 2-coloring $\mathcal{C}$ of $m{C}_{2n}$, i.e., the set of the vertex weights consists of two numbers ${\mathcal{C}}_1$ and ${\mathcal{C}}_2$. As every edge label contributes exactly once to the vertex weight of a vertex colored ${\mathcal{C}}_1$ we obtain

$$mn·{\mathcal{C}}_1=1+2+\cdots +2nm.$$

However, every edge label contributes also exactly once to the vertex weight of a vertex colored ${\mathcal{C}}_2$ thus

$$mn·{\mathcal{C}}_2=1+2+\cdots +2nm.$$

A contradiction. Thus, ${\chi }_{la}(m{C}_{2n})\ge 3$. □

Theorem 4.

Let n, m be positive integers, $n\ge 1$, $m\ge 1$. Then

$${\chi }_{la}(m{C}_{2n+1})\le m+2.$$

Proof. 

Let us denote the vertex set and the edge set of $m{C}_{2n+1}$ such that $V(C_{2n+1})=\{v_i^j:i=1,2,\cdots ,2n+1,j=1,2,\cdots ,m\}$ and $E(C_{2n+1})=\{v_i^j{v}_{i+1}^j:i=1,2,\cdots ,2n,j=1,2,\cdots ,m\}\cup \{v_1^j{v}_{2n+1}^j:j=1,2,\cdots ,m\}$. Let $e_i^j=v_i^j{v}_{i+1}^j$, $i=1,2,\cdots ,2n$, $j=1,2,\cdots ,m$ and let $e_{2n+1}^j=v_1^j{v}_{2n+1}^j$, $j=1,2,\cdots ,m$.

We define an edge labeling f of $m{C}_{2n+1}$ in the following way

$$\begin{array}{c}\hfill f(e_i^j)=\left\{\begin{array}{cc}\frac{m(i-1)}{2}+j,\hfill & \mathrm{if}i=1,3,\cdots ,2n+1,j=1,2,\cdots ,m,\hfill \\ m\left(2n+2-\frac{i}{2}\right)+1-j,\hfill & \mathrm{if}i=2,4,\cdots ,2n,j=1,2,\cdots ,m.\hfill \end{array}\right.\end{array}$$

For the weight of the vertex $v_i^j$, $i=3,5,\cdots ,2n+1$, $j=1,2,\cdots ,m$ we obtain

$$\begin{array}{cc}\hfill w{t}_f(v_i^j)=& f(e_{i-1}^j)+f(e_i^j)=\left[m\left(2n+2-\frac{i-1}{2}\right)+1-j\right]+\left[\frac{m(i-1)}{2}+j\right]=m(2n+2)+1\hfill \end{array}$$

and for $i=2,4,\cdots ,2n$, $j=1,2,\cdots ,m$, we obtain

$$\begin{array}{cc}\hfill w{t}_f(v_i^j)=& f(e_{i-1}^j)+f(e_i^j)=\left[\frac{m((i-1)-1)}{2}+j\right]+\left[m\left(2n+2-\frac{i}{2}\right)+1-j\right]\hfill \\ \hfill =& m(2n+1)+1.\hfill \end{array}$$

The weight of the vertex $v_1^j$, $j=1,2,\cdots ,m$, is

$$\begin{array}{cc}\hfill w{t}_f(v_1^j)=& f(e_1^j)+f(e_{2n+1}^j)=\left[\frac{m(1-1)}{2}+j\right]+\left[\frac{m((2n+1)-1)}{2}+j\right]=mn+2j,\hfill \end{array}$$

thus the weights are $mn+2,mn+4,\cdots ,m(n+2)$. Thus, all adjacent vertices have distinct weights. Moreover we obtain ${\chi }_{la}(m{C}_{2n+1})\le m+2$. □

Please note that a cycle $C_{2n+1}$ is 1-equally 2-edge colorable. It is possible to generalize the results from the previous section also for $c(G)$-equally 2-edge colorable graphs. If we are able to guarantee that for every edge $uv\in E(G)$ is

$$\begin{array}{cc}\hfill mw{t}_f(u)+(i-m)n_c^1(u)+& (1-i)n_c^2(u)\hfill \\ & \ne mw{t}_f(v)+(i-m)n_c^1(v)+(1-i)n_c^2(v)\hfill \end{array}$$

(3)

then we can prove that

$${\chi }_{la}(mG)\le {\chi }_{la}(G)+min\{(m-1)c(G):c\mathrm{is}\mathrm{a}2\text{-}\mathrm{edge}\mathrm{coloring}\mathrm{of}G\mathrm{satisfying}(3)\}.$$

This condition is fulfilled for some graphs containing pendant vertices, thus also for some trees.

Lemma 2.

Let G be a graph with l leaves, $l\ge 0$. Then

$${\chi }_{la}(G)\ge l+1.$$

Proof. 

The proof is similar to the proof in [14]. Let f be any local antimagic labeling of a graph G. Then in the coloring induced by f, the color of a leaf v is $f(uv)$, where $uv\in E(G)$. Hence all the leaves receive distinct colors. Moreover, for any non-leaf w incident with an edge e with $f(e)=|E(G)|$, the color assigned to w is larger than $|E(G)|$. Hence the number of colors in the coloring induced by f is at least $l+1$. □

Theorem 5.

Let G be a graph without a component isomorphic to $K_2$ such that all vertices in G but leaves have the same even degree. If there exists a 2-edge coloring c of G such that for all vertices v but leaves holds $n_c^1(v)=n_c^2(v)=\mathrm{deg}(v)/2$, then

$$ml+1\le {\chi }_{la}(mG)\le {\chi }_{la}(G)+(m-1)l,$$

where m is a positive integer and l is the number of leaves in G.

Proof. 

Let G be a graph without a component isomorphic to $K_2$ such that all its vertices but leaves have the same even degree $2r$. Let c be a 2-edge coloring of G such that for all vertices v in G but leaves holds $n_c^1(v)=n_c^2(v)=\mathrm{deg}(v)/2=r$.

Let f be any local antimagic labeling of a graph G that uses ${\chi }_{la}(G)$ colors. Then using Equality (1) we obtain that there exists an edge labeling g of $mG$, $m\ge 1$, such that the weights of non-leaf vertices $v_i$, $i=1,2,\cdots ,m$, corresponding to a vertex v in G, are

$$\begin{array}{c}\hfill w{t}_g(v_i)=m·w{t}_f(v)+(1-m)r.\end{array}$$

This means that the weights of corresponding non-leaf vertices in every copy of G are the same. However, this also means that the adjacent non-leaf vertices in $mG$ have distinct weights.

Now consider the edges $w_i{u}_i$, $i=1,2,\cdots ,m$, where w is a leaf. For $i=1,2,\cdots ,m$ trivially holds

$$w{t}_g(w_i)=g(w_i{u}_i)<{\displaystyle \sum _{uv\in E(G)}}g(v_i{u}_i)=w{t}_g(u_i).$$

Which means that all adjacent vertices have distinct weights.

Combining the previous arguments we obtain

$${\chi }_{la}(mG)\le {\chi }_{la}(G)+(m-1)l.$$

The lower bound for ${\chi }_{la}(mG)$ follows from Lemma 2. □

3. Trees

If the graph in Theorem 5 is a forest we immediately obtain the following result.

Theorem 6.

Let T be a forest with no component isomorphic to $K_2$ such that all vertices but leaves have the same even degree. Then

$$ml+1\le {\chi }_{la}(mT)\le {\chi }_{la}(T)+(m-1)l,$$

where m is a positive integer and l is the number of leaves in T.

Proof. 

Trivially, any graph containing $K_2$ as a component cannot be local antimagic.

Let T be a forest with no component isomorphic to $K_2$ such that all vertices but leaves have the same even degree $2r$. Clearly there exists a 2-edge coloring c of T such that for all vertices v but leaves hold $n_c^1(v)=n_c^2(v)=\mathrm{deg}(v)/2=r$. Thus, according to Theorem 5 we are done. □

Immediately from the previous theorem we obtain the result for copies of paths and copies of some stars as ${\chi }_{la}(P_n)=3$ for $n\ge 3$ and ${\chi }_{la}(K_{1,n})=n+1$ for $n\ge 2$, see [14].

Corollary 2.

Let $P_n$ be a path on n vertices, $n\ge 3$. Then for every positive integer m, $m\ge 1$, holds

$${\chi }_{la}(m{P}_n)=2m+1.$$

Corollary 3.

Let $K_{1,2n}$ be a star, $n\ge 1$. Then for every positive integer m, $m\ge 1$, holds

$${\chi }_{la}(m{K}_{1,2n})=2nm+1.$$

Theorem 7.

Let $K_{1,2n+1}$ be a star, $n\ge 1$. Then for every positive integer m, $m\ge 1$, holds

$${\chi }_{la}(m{K}_{1,2n+1})=\left\{\begin{array}{cc}(2n+1)m+1,\hfill & \mathit{if}m\mathit{is}\mathit{odd}\mathit{or}\mathit{if}m\mathit{is}\mathit{even}\mathit{and}m\ge n+1,\hfill \\ (2n+1)m+2,\hfill & \mathit{if}m\mathit{is}\mathit{even}\mathit{and}m<n+1.\hfill \end{array}\right.$$

Proof. 

Let us denote the vertices and the edges of $m{K}_{1,2n+1}$ such that

$$\begin{array}{cc}\hfill V(m{K}_{1,2n+1})=& \{w_i,v_i^j:i=1,2,\cdots ,m,j=1,2,\cdots ,2n+1\},\hfill \\ \hfill E(m{K}_{1,2n+1})=& \{w_i{v}_i^j:i=1,2,\cdots ,m,j=1,2,\cdots ,2n+1\}.\hfill \end{array}$$

We consider two cases according to the parity of m.

Case 1: when m is odd.

We define an edge labeling g of $m{K}_{1,2n+1}$ in the following way

$$g(w_i{v}_i^j)=\left\{\begin{array}{cc}i,\hfill & \mathrm{if}j=1\mathrm{and}i=1,2,\cdots ,m,\hfill \\ \frac{3m+1}{2}+i,\hfill & \mathrm{if}j=2\mathrm{and}i=1,2,\cdots ,\frac{m-1}{2},\hfill \\ \frac{m+1}{2}+i,\hfill & \mathrm{if}j=2\mathrm{and}i=\frac{m+1}{2},\frac{m+3}{2},\cdots ,m,\hfill \\ 3m+1-2i,\hfill & \mathrm{if}j=3\mathrm{and}i=1,2,\cdots ,\frac{m-1}{2},\hfill \\ 4m+1-2i,\hfill & \mathrm{if}j=3\mathrm{and}i=\frac{m+1}{2},\frac{m+3}{2},\cdots ,m,\hfill \\ (j-1)m+i,\hfill & \mathrm{if}j=4,5,\cdots ,n+2\mathrm{and}i=1,2,\cdots ,m,\hfill \\ jm+1-i,\hfill & \mathrm{if}j=n+3,n+4,\cdots ,2n+1\mathrm{and}i=1,2,\cdots ,m.\hfill \end{array}\right.$$

Evidently g is a bijection and the induced weights of the vertices $w_i$, $i=1,2,\cdots ,m$, are

$$w{t}_g(w_i)={\displaystyle \sum _{j=1}^{2n+1}}g(w_i{v}_i^j)=\frac{(2n+1)(m(2n+1)+1)}{2}.$$

As all vertices of degree $2n+1$ have the same weights and the weights of the leaves are distinct we obtain ${\chi }_{la}(m{K}_{1,2n+1})\le (2n+1)m+1$. The lower bound follows from Lemma 2.

Case 2: when m is even.

In this case consider a labeling f of $m{K}_{1,2n+1}$ defined such that

$$f(w_i{v}_i^j)=\left\{\begin{array}{cc}j,\hfill & \mathrm{if}j=1,2,\cdots ,2n+1\mathrm{and}i=1,\hfill \\ 2n+1+g(w_{i-1}{v}_{i-1}^j),\hfill & \mathrm{if}j=1,2,\cdots ,2n+1\mathrm{and}i=2,3,\cdots ,m.\hfill \end{array}\right.$$

According to the properties of the labeling g, the labeling f is a bijective mapping that assigns numbers $1,2,\cdots ,m(2n+1)$ to the edges of $m{K}_{1,2n+1}$. The weights of vertices $w_i$, $i=2,3,\cdots ,m$, are all the same as

$$\begin{array}{cc}\hfill w{t}_f(w_i)=& {\displaystyle \sum _{j=1}^{2n+1}}f(w_i{v}_i^j)={\displaystyle \sum _{j=1}^{2n+1}}\left[2n+1+g(w_{i-1}{v}_{i-1}^j)\right]={(2n+1)}^2+\frac{(2n+1)(m(2n+1)+1)}{2}.\hfill \end{array}$$

The weight of the vertex $w_1$ is

$$w{t}_f(w_1)={\displaystyle \sum _{j=1}^{2n+1}}f(w_1{v}_1^j)={\displaystyle \sum _{j=1}^{2n+1}}j=(n+1)(2n+1).$$

If the weight of the vertex $w_1$ under the labeling f is the same as the weight of some leaf, we obtain that ${\chi }_{la}(m{K}_{1,2n+1})\le (2n+1)m+1$. This is satisfied when $(n+1)(2n+1)\le m(2n+1)$, that is if $n+1\le m$. The equality ${\chi }_{la}(m{K}_{1,2n+1})=(2n+1)m+1$ holds because the number of induced colors must be greater then the number of leaves, see Lemma 2.

Now consider that the weight of the vertex $w_1$ under the labeling f is greater then the weight of all leaves, i.e., $n+1>m$. Then labeling f induces $(2n+1)m+2$ colors for vertices.

To prove that it is not possible to obtain $(2n+1)m+1$ colors it is sufficient to consider the fact, that the weight of any vertex of degree $2n+1$ is at least the sum of numbers $1,2,\cdots ,2n+1$, thus it is at least $(n+1)(2n+1)$. However, the weights of leaves are at most $(2n+1)m$. Thus if there exists an edge labeling that induces $(2n+1)m+1$ colors for vertices, under this labeling all vertices $w_i$, $i=1,2,\cdots ,m$ must have the same color/weight, say $c(w)$. However, in this case the sum of all edge labels must be equal to m multiple of $c(w)$, as every edge label contributes exactly once the weight of a vertex of degree $2n+1$. Thus $mc(w)=1+2+\cdots +(2n+1)m$ which implies

$$\begin{array}{cc}\hfill 2c(w)=& (2n+1)((2n+1)m+1).\hfill \end{array}$$

However, this is a contradiction as for m even the right side of the previous equation is odd. This means that in this case ${\chi }_{la}(m{K}_{1,2n+1})=(2n+1)m+2$. □

Please note that Theorem 6 can be extended also for other trees (forests) such that their non-leaf vertices have even degrees, not necessarily the same. We just need to guarantee that the adjacent non-leaf vertices will have distinct weights. For some trees, for example for spiders, we are able to do it. A spider graph is a tree with exactly one vertex of degree greater than 2. By $S(n_1,n_2,\cdots ,n_l)$, $1\le n_i\le n_{i+1}$, $i=1,2,\cdots ,l-1$, $l\ge 3$, we denote a spider obtained by identifying one leaf in paths $P_{n_i+1}$, $i=1,2,\cdots ,l$. In [17] was proved that if $n_1=1$ then ${\chi }_{la}(S(n_1,n_2,\cdots ,n_l))=l+1$ and if $n_1\ge 2$ then ${\chi }_{la}(S(n_1,n_2,\cdots ,n_l))\le l+2$. Moreover, for $l\ge 4$ the described edge labeling induces for the root vertex, the vertex of degree l, the largest weight over all other vertex weights. Using the presented results we obtain

Theorem 8.

Let $S(n_1,n_2,\cdots ,n_l)$ be a spider graph. If l is even, $l\ge 4$, and $n_1=1$

$$\begin{array}{c}\hfill {\chi }_{la}(mS(n_1,n_2,\cdots ,n_l))=ml+1.\end{array}$$

If l is even, $l\ge 4$, and $n_1\ge 2$

$$\begin{array}{c}\hfill ml+1\le {\chi }_{la}(mS(n_1,n_2,\cdots ,n_l))\le ml+2.\end{array}$$

In [18] was proposed the following conjecture.

Theorem 9.

Ref. [18] Let T be a tree other than $K_2$ with l leaves. Then

$$l+1\le {\chi }_{la}(T)\le l+2.$$

In the light of the previous results trees, for copies of trees we conjecture

Theorem 10.

Let T be a tree other than $K_2$ with l leaves. Then for every positive integer m, $m\ge 1$,

$$ml+1\le {\chi }_{la}(mT)\le ml+2.$$

4. Graphs with Chromatic Index 3

In this section we will deal with 3-regular graphs that admit a proper 3-edge coloring.

Theorem 11.

Let G be a 3-regular graph with chromatic index ${\chi }^{\prime }(G)=3$. Then for every odd positive integer m, $m\ge 1$, holds

$${\chi }_{la}(mG)\le {\chi }_{la}(G).$$

Proof. 

Let c be a proper 3-edge coloring of G. Let f be a local vertex antimagic edge labeling of G that uses ${\chi }_{la}(G)$ colors.

We define a new labeling g of $mG$, for m odd, in the following way.

$$g(e_i)=\left\{\begin{array}{cc}m(f(e)-1)+i,\hfill & \mathrm{if}c(e)=c_1\mathrm{and}i=1,2,\cdots ,m,\hfill \\ m(f(e)-1)+i+\frac{m+1}{2},\hfill & \mathrm{if}c(e)=c_2\mathrm{and}i=1,2,\cdots ,\frac{m-1}{2},\hfill \\ m(f(e)-1)+i-\frac{m-1}{2},\hfill & \mathrm{if}c(e)=c_2\mathrm{and}i=\frac{m+1}{2},\frac{m+3}{2},\cdots ,m,\hfill \\ mf(e)+1-2i,\hfill & \mathrm{if}c(e)=c_3\mathrm{and}i=1,2,\cdots ,\frac{m-1}{2},\hfill \\ mf(e)+m+1-2i,\hfill & \mathrm{if}c(e)=c_3\mathrm{and}i=\frac{m+1}{2},\frac{m+3}{2},\cdots ,m.\hfill \end{array}\right.$$

It is easy to see that if an edge in G is labeled with the number t, $1\le t\le |E(G)|$, then the corresponding edges in $mG$ are labeled with numbers from the set $\{m(t-1)+1,m(t-1)+2,\cdots ,mt\}$. Thus, g is a bijection that assigns numbers $1,2,\cdots ,m|E(G)|$ to the edges of $mG$.

Now we will calculate a vertex weight of the vertex $v_i$ in $mG$. Let $x,y$ and z be the vertices adjacent to v in G. Without loss of generality we can assume that $c(xv)=c_1$, $c(yv)=c_2$ and $c(zv)=c_3$. Then for $i=1,2,\cdots ,(m-1)/2$ we obtain

$$\begin{array}{cc}\hfill w{t}_g(v_i)& =g(x_i{v}_i)+g(y_i{v}_i)+g(z_i{v}_i)\hfill \\ & =\left[m(f(xv)-1)+i\right]+\left[m(f(yv)-1)+i+\frac{m+1}{2}\right]+\left[mf(zv)+1-2i\right]\hfill \\ & =m(f(xv)+f(yv)+f(zv))+\frac{3-3m}{2}=mw{t}_f(v)+\frac{3-3m}{2}.\hfill \end{array}$$

If $i=(m+1)/2,(m+3)/2,\cdots ,m$ then

$$\begin{array}{cc}\hfill w{t}_g(v_i)& =g(x_i{v}_i)+g(y_i{v}_i)+g(z_i{v}_i)\hfill \\ & =\left[m(f(xv)-1)+i\right]+\left[m(f(yv)-1)+i-\frac{m-1}{2}\right]+\left[mf(zv)+m+1-2i\right]\hfill \\ & =m(f(xv)+f(yv)+f(zv))+\frac{3-3m}{2}=mw{t}_f(v)+\frac{3-3m}{2}.\hfill \end{array}$$

(4)

Thus, in all copies the corresponding vertices have the same weights.

Moreover, as the set of weights of vertices in G under the labeling f consists of ${\chi }_{la}(G)$ distinct numbers we immediately obtain that also the set of weights of vertices in $mG$ under the labeling g consists of ${\chi }_{la}(G)$ distinct numbers. Thus, ${\chi }_{la}(mG)\le {\chi }_{la}(G)$. □

Analogously, as it was possible to extend the results in Section 2 for graphs with leaves, we can also extend Theorem 11 for some graphs with pendant vertices.

Theorem 12.

Let G be a graph such that all vertices but leaves have degree 3. If there exists a 3-edge coloring c of G such that for all vertices v but leaves hold $n_c^1(v)=n_c^2(v)=n_c^3(v)=1$, then for every odd positive integer m, $m\ge 1$,

$$ml+1\le {\chi }_{la}(mG)\le {\chi }_{la}(G)+(m-1)l,$$

where l is the number of leaves in G.

Proof. 

Let G be a graph such that all its vertices but leaves have degree 3. Let c be a 3-edge coloring of G such that for all vertices v in G but leaves hold $n_c^1(v)=n_c^2(v)=n_c^3(v)=1$.

Let f be any local antimagic labeling of a graph G that uses ${\chi }_{la}(G)$ colors. Then using Equality (4) we obtain that there exists an edge labeling g of $mG$, m odd $m\ge 1$, such that the weights of non-leaf vertices $v_i$, $i=1,2,\cdots ,m$, corresponding to a vertex v in G, are

$$\begin{array}{c}\hfill w{t}_g(v_i)=mw{t}_f(v)+\frac{3-3m}{2}.\end{array}$$

This means that the weights of corresponding non-leaf vertices in every copy of G are the same. However, this also means that the adjacent non-leaf vertices in $mG$ have distinct weights.

Now consider the edges $w_i{u}_i$, $i=1,2,\cdots ,m$, where w is a leaf. Trivially holds

$$w{t}_g(w_i)=g(w_i{u}_i)<{\displaystyle \sum _{uv\in E(G)}}g(v_i{u}_i)=w{t}_g(u_i).$$

Which means that all adjacent vertices have distinct weights.

Combining the previous arguments we obtain

$${\chi }_{la}(mG)\le {\chi }_{la}(G)+(m-1)l.$$

The lower bound for ${\chi }_{la}(mG)$ follows from Lemma 2. □

Immediately for forests we obtain the following result.

Corollary 4.

Let T be a forest such that all its vertices but leaves have degree 3. Then for every odd positive integer m, $m\ge 1$ holds

$$ml+1\le {\chi }_{la}(mT)\le {\chi }_{la}(T)+(m-1)l,$$

where l is the number of leaves in T.

Proof. 

Let T be a forest such that all its vertices but leaves have degree 3. Trivially there exists a 3-edge coloring c of T such that for all vertices v but leaves hold $n_c^1(v)=n_c^2(v)=n_c^3(v)=1$. Using Theorem 12 we obtain the desired result. □

The next theorem shows how it is possible to extend the previous result for regular graphs that are decomposable into spanning subgraphs that are all isomorphic either to even regular graphs or 3-regular graphs.

Theorem 13.

Let G be a graph that can be decomposed into factors $G_1,G_2,$$\cdots ,G_k$, $k\ge 1$, and let every factor $G_i$, $i=1,2,\cdots ,k$, be isomorphic to a graph of the following types:

• type I: a 4-regular graph,
• type II: a 2-regular graph consisting of even cycles,
• type III: a 3-regular graph with chromatic index 3.

If every factor $G_i$, $i=1,2,\cdots ,k$, is of type I or of type II then for every positive integer m, $m\ge 1$, holds

$${\chi }_{la}(mG)\le {\chi }_{la}(G).$$

If at least one factor $G_i$, $i=1,2,\cdots ,k$, is of type III then for every odd positive integer m, $m\ge 1$, holds

$${\chi }_{la}(mG)\le {\chi }_{la}(G).$$

Please note that the exact value of ${\chi }_{la}(K_n)$ is n, since ${\chi }_{la}(K_n)\ge \chi (K_n)=n$. Immediately from the previous theorem we obtain the following result for complete graphs $K_n$.

Corollary 5.

Let $K_n$ be a complete graph on n vertices, $n\ge 4$. If $n\equiv 1(mod4)$ then for every positive integer m, $m\ge 1$, and if $n\equiv 0(mod4)$ then for every odd positive integer m, $m\ge 1$, we have ${\chi }_{la}(m{K}_n)=n$.

5. Conclusions

One interesting problem is to find a local antimagic chromatic number for disjoint union of arbitrary graphs. According to results proved by Haslegrave [16] we obtain that this parameter is finite for disjoint union of arbitrary graphs if and only if non of these graphs contains an isolated edge as a subgraph. Moreover, Haslegrave [16] proved the following result.

Theorem 14.

Ref. [16] For every graph G with m edges, none of which is isolated, and for any positive integer k, the edges of G may be labeled with a permutation of $\{k,k+1,\cdots ,m+k-1\}$ in such a way that the vertex sums distinguish all pairs of adjacent vertices.

Immediately from this result we obtain an upper bound for a local antimagic chromatic number for disjoint union of arbitrary graphs.

Theorem 15.

Let $G_i$, $i=1,2,\cdots ,n$, be a graph with no isolated edge. Then

$${\chi }_{la}\left({\displaystyle \bigcup _{i=1}^n}{G}_i\right)\le min\left\{{\chi }_{la}(G_t)+{\displaystyle \sum _{i=1}^n}|V(G_i)|-|V(G_t)|:t=1,2,\cdots ,n\right\}.$$

For some graphs we can obtain a better upper bound.

Theorem 16.

Let $G_i$, $i=1,2$, be a graph with no isolated edge. Let $G_2$ be a graph such that all vertices but leaves have the same degree. Then

$${\chi }_{la}(G_1\cup G_2)\le {\chi }_{la}(G_1)+{\chi }_{la}(G_2)+l_2,$$

where $l_2$ is the number of leaves in $G_2$.

Proof. 

Let $G_2$ be a graph such that all vertices but leaves have the same degree r, $r\ge 2$ and let $l_2$ be the number of leaves in $G_2$. Let $f_i$, $i=1,2$, be a local vertex antimagic edge labeling of $G_i$ that uses ${\chi }_{la}(G_i)$ colors. We define an edge labeling g of $G_1\cup G_2$ such that

$$g(e)=\left\{\begin{array}{cc}{f}_1(e),\hfill & \mathrm{if}e\in E(G_1),\hfill \\ f_2(e)+\left|E(G_1)\right|,\hfill & \mathrm{if}e\in E(G_2).\hfill \end{array}\right.$$

As $f_1$ and $f_2$ are bijections evidently also g is a bijection. For the vertex weights under the labeling g we obtain the following. If $v\in V(G_1)$ then

$$\begin{array}{cc}\hfill w{t}_g(v)=& {\displaystyle \sum _{uv\in E(G_1)}}g(uv)={\displaystyle \sum _{uv\in E(G_1)}}{f}_1(uv)=w{t}_{f_1}(v).\hfill \end{array}$$

Thus, the weights of adjacent vertices in $G_1$ are distinct and they induce ${\chi }_{la}(G_1)$ colors.

If $v\in V(G_2)$ and ${\mathrm{deg}}_{G_2}(v)=r$ then

$$\begin{array}{cc}\hfill w{t}_g(v)=& {\displaystyle \sum _{uv\in E(G_2)}}g(uv)={\displaystyle \sum _{uv\in E(G_2)}}(f_2(uv)+|E(G_1)|)\hfill \\ \hfill =& {\displaystyle \sum _{uv\in E(G_2)}}{f}_2(uv)+r|E(G_1)|=w{t}_{f_2}(v)+r\left|E(G_1)\right|.\hfill \end{array}$$

If $v\in V(G_2)$ and ${\mathrm{deg}}_{G_2}(v)=1$ then

$$\begin{array}{cc}\hfill w{t}_g(v)=& {\displaystyle \sum _{uv\in E(G_2)}}g(uv)={\displaystyle \sum _{uv\in E(G_2)}}(f_2(uv)+|E(G_1)|)=f_2(uv)+\left|E(G_1)\right|\hfill \\ \hfill =& w{t}_{f_2}(v)+\left|E(G_1)\right|.\hfill \end{array}$$

This means that also the weights of adjacent vertices in $G_2$ are distinct. Moreover, we obtain that the labeling g induces at most ${\chi }_{la}(G_2)+l_2$ colors as the number of colors assigned to the vertices of degree at least 2 is the same and all the leaves could be assigned with the colors different from the colors of non leaves.

Combining the previous we obtain that the labeling g induces at most ${\chi }_{la}(G_1)+{\chi }_{la}(G_2)+l_2$ colors. □

Theorem 17.

Let G be a graph with no isolated edge and with l leaves. Then for every positive integer m, $m\ge 1$ holds

$$l+2m+1\le {\chi }_{la}(G\cup m{P}_3)\le {\chi }_{la}(G)+2m+1.$$

Proof. 

Let G be a graph with no isolated edge and with l leaves. The lower bound follows from Lemma 2. The upper bound is based on the fact that there exists a local antimagic labeling of $m{P}_3$ that induces $2m+1$ colors such that the color of every vertex of degree 2 in $m{P}_3$ will have the same color $2m+1$. Thus, the labeling g of $m{P}_3\cup G$ described in the proof of Theorem 16 induces also $2m+1$ colors for vertices in $m{P}_3$. These colors are $|E(G)|+1,|E(G)|+2,\cdots ,|E(G)|+2m$ and $2|E(G)|+2m+1$. In general, these colors are distinct from colors of vertices in $G_1$ induced by the labeling g. This concludes the proof. □