Opuscula Math. 43, no. 6 (2023), 841-864
https://doi.org/10.7494/OpMath.2023.43.6.841

Opuscula Mathematica

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)

1. S. Arumugam, K. Premalatha, M. Bača, A. Semaničová-Feňovčíková, Local antimagic vertex coloring of a graph, Graphs Combin. 33 (2017), 275-285. https://doi.org/10.1007/s00373-017-1758-7
2. J. Bensmail, M. Senhaji, K. Szabo Lyngsie, On a combination of the 1-2-3 conjecture and the antimagic labelling conjecture, Discrete Math. Theoret. Comput. Sci. 19 (2017), no. 1, Paper no. 22. https://doi.org/10.23638/DMTCS-19-1-21
3. J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, New York, MacMillan, 1976.
4. J. Haslegrave, Proof of a local antimagic conjecture, Discrete Math. Theoret. Comput. Sci. 20 (2018), no. 1, Paper no. 18.
5. M. Kraitchik, Magic Squares, Mathematical Recreations, New York, Norton, 1942, pp. 142-192.
6. G.C. Lau, J. Li, W.C. Shiu, Approaches which output infinitely many graphs with small local antimagic chromatic number, Discrete Math. Algorithms Appl. 15 (2023), no. 2, 2250079. https://doi.org/10.1142/S1793830922500793
7. G.C. Lau, H.K. Ng, W.C. Shiu, Affirmative solutions on local antimagic chromatic number, Graphs Combin. 36 (2020), no. 5, 1337-1354. https://doi.org/10.1007/s00373-020-02197-2
8. G.C. Lau, H.K. Ng, W.C. Shiu, Cartesian magicness of 3-dimensional boards, Malaya J. Matematik 8 (2020), no. 3, 1175-1185. https://doi.org/10.26637/MJM0803/0077
9. G.C. Lau, W.C. Shiu, H.K. Ng, On local antimagic chromatic number of cycle-related join graphs, Discuss. Math. Graph Theory 41 (2021), 133-152. https://doi.org/10.7151/dmgt.2177
10. S.A. Pratama, S. Setiawani, Slamin, Local super antimagic total vertex coloring of some wheel related graphs, J. Phys. Conf. Ser. 1538 (2020), 012014. https://doi.org/10.1088/1742-6596/1538/1/012014
11. S. Slamin, N.O. Adiwijaya, M.A. Hasan, D. Dafik, K. Wijaya, Local super antimagic total labeling for vertex coloring of graphs, Symmetry 2020 12(11), 1843. https://doi.org/10.3390/sym12111843
12. D. Zuckerman, Linear degree extractors and the inapproximability of max clique and chromatic number, Theory Comput. 3 (2007), 103-128. https://doi.org/10.4086/toc.2007.v003a006
• Gee-Choon Lau (corresponding author)
• https://orcid.org/0000-0002-9777-6571
• Universiti Teknologi MARA (Segamat Campus), College of Computing, Informatics & Mathematics, 85000, Johor, Malaysia
• Karl Schaffer
• De Anza College, Mathematics Department, Cupertino, California, USA
• Communicated by Andrzej Żak.
• Revised: 2023-05-05.
• Accepted: 2023-05-05.
• Published online: 2023-07-22.