Every graph is local antimagic total and its applications

Abstract

Let $G=(V,E)$ be a simple graph of order $p$ and size $q$. A graph $G$ is called local antimagic (total) if $G$ admits a local antimagic (total) labeling. A bijection $g : E \to {1,2,\ldots,q}$ is called a local antimagic labeling of $G$ if for any two adjacent vertices $u$ and $v$, we have $g^+(u) \neq g^+(v)$, where $g^+(u) = \sum_{e\in E(u)} g(e)$, and $E(u)$ is the set of edges incident to $u$. Similarly, a bijection $f:V(G)\cup E(G)\to {1,2,\ldots,p+q}$ is called a local antimagic total labeling of $G$ if for any two adjacent vertices $u$ and $v$, we have $w_f(u)\neq w_f(v)$, where $w_f(u) = f(u) + \sum_{e\in E(u)} f(e)$. Thus, any local antimagic (total) labeling induces a proper vertex coloring of $G$ if vertex $v$ is assigned the color $g^{+}(v)$ (respectively, $w_{f}(u)$). The local antimagic (total) chromatic number, denoted $\chi_{lat}(G)$ (respectively $\chi_{lat}(G)$), is the minimum number of induced colors taken over local antimagic (total) labeling of $G$. We provide a short proof that every graph $G$ is local antimagic total. The proof provides sharp upper bound to $\chi_{lat}(G)$. We then determined the exact $\chi_{lat}(G)$, where $G$ is a complete bipartite graph, a path, or the Cartesian product of two cycles. Consequently, the $\chi_{la}(G\vee K_1)$ is also obtained. Moreover, we determined the $\chi_{la}(G\vee K_1)$ and hence the $\chi_{lat}(G)$ for a class of 2-regular graphs $G$ (possibly with a path). The work of this paper also provides many open problems on $\chi_{lat}(G)$. We also conjecture that each graph $G$ of order at least 3 has $\chi_{lat}(G)\leq \chi_{la}(G)$.