Opuscula Math. 43, no. 3 (2023), 429-453
https://doi.org/10.7494/OpMath.2023.43.3.429
Opuscula Mathematica
On local antimagic total labeling of complete graphs amalgamation
Abstract. Let \(G = (V,E)\) be a connected 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 $ if for any two adjacent vertices \(u\) and \(v\), we have \(g^+(u) \ne 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)\ne 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\). In this paper, we determined \(\chi_{lat}(G)\) where \(G\) is the amalgamation ofcomplete graphs. Consequently, we also obtained the local antimagic (total) chromatic number of the disjoint union of complete graphs, and the join of \(K_1\) and amalgamation of complete graphs under various conditions. An application of local antimagic total chromatic number is also given.
Keywords: local antimagic (total) chromatic number, amalgamation, complete graphs.
Mathematics Subject Classification: 05C78, 05C15.
- 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.
- J. Bensmail, M. Senhaji, K.S. Lyngsie, On a combination of the 1-2-3 conjecture and the antimagic labelling conjecture, Discrete Math. Theoret. Comput. Sci. 19 (2017), no. 1, #22.
- J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, New York, MacMillan, 1976.
- T.R. Hagedorn, Magic rectangles revisited, Discrete Math. 207 (1999), 65-72.
- J. Haslegrave, Proof of a local antimagic conjecture, Discrete Math. Theor. Comput. Sci. 20 (2018), no. 1, #18.
- G.C. Lau, J. Li, H.K. Ng, W.C. Shiu, Approaches which output infinitely many graphs with small local antimagic chromatic number, Disc. Math. Algorithms Appl. 15 no. 2, 2250079 (2023). https://doi.org/10.1142/S1793830922500793
- G.C. Lau, H.K. Ng, W.C. Shiu, Affirmative solutions on local antimagic chromatic number, Graphs Combin. 36 (2020), 1337-1354.
- G.C. Lau, K. Schaeffer, W.C. Shiu, Every graph is local antimagic total and its applications, (2022), preprint.
- G.C. Lau, W.C. Shiu, H.K. Ng, On local antimagic chromatic number of graphs with cut-vertices, Iran. J. Math. Sci. Inform. (2022), accepted.
- 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
- G.C. Lau, W.C. Shiu, C.X. Soo, On local antimagic chromatic number of spider graphs, J. Discrete Math. Sci. Cryptogr. (2022), published online. https://doi.org/10.1080/09720529.2021.1892270
- K. Premalatha, S. Arumugam, Y-C. Lee, T.-M. Wang, Local antimagic chromatic number of trees - I, J. Discrete Math. Sci. Cryptogr. 25 (2022), no. 6, 1591-1602. https://doi.org/10.1080/09720529.2020.1772985
- W.C. Shiu, P.C.B. Lam, S.M. Lee, On a construction of supermagic graphs, J. Comb. Math. Comb. Comput. 42 (2002), 147-160.
- 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 & Media, 85000 Johor, Malaysia
- Wai Chee Shiu
- https://orcid.org/0000-0002-2819-8480
- The Chinese University of Hong Kong, Department Mathematics, Shatin, Hong Kong
- Communicated by Andrzej Żak.
- Received: 2022-05-04.
- Revised: 2023-03-27.
- Accepted: 2023-03-28.
- Published online: 2023-05-17.
