Every graph is local antimagic total and its applications

Gee-Choon Lau
Karl Schaffer
Wai Chee Shiu

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_{la}(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)\).

Keywords: local antimagic (total) chromatic number, Cartesian product, join product.

Mathematics Subject Classification: 05C78, 05C15.

Full text (pdf)