Every graph is local antimagic total and its applications

• Autorzy: Lau Gee-Choon , Schaffer Karl , Shiu Wai-Chee

Identyfikatory

DOI

10.7494/OpMath.2023.43.6.841

• Języki publikacji: EN

Abstrakty

EN

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 → {1, 2, . . . , q} is called a local antimagic labeling of G if for any two adjacent vertices u and v, we have g+(u)≠g+(v), where g+(u) = ∑e∈E(u) g(e), and E(u) is the set of edges incident to u. Similarly, a bijection f : V (G)∪E(G) → {1, 2, . . . , p+q} is called a local antimagic total labeling of G if for any two adjacent vertices u and v, we have wf (u)≠wf (v), where wf (u) = f(u) + ∑e∈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, wf (u)). The local antimagic (total) chromatic number, denoted χla(G) (respectively χ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 χlat(G). We then determined the exact χlat(G), where G is a complete bipartite graph, a path, or the Cartesian product of two cycles. Consequently, the χla(G ∨ K1) is also obtained. Moreover, we determined the χla(G ∨ K1) and hence the χ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 χlat(G). We also conjecture that each graph G of order at least 3 has χlat(G) ≤ χla(G).

Słowa kluczowe

EN

local antimagic (total) chromatic number; Cartesian product; join product

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2023
• Tom: Vol. 43, no. 6
• Strony: 841--864
• Opis fizyczny: Bibliogr. 12 poz., tab.

Twórcy

autor

Lau Gee-Choon

• Universiti Teknologi MARA (Segamat Campus), College of Computing, Informatics & Mathematics, 85000, Johor, Malaysia

• https://orcid.org/0000-0002-9777-6571

autor

Schaffer Karl

• De Anza College, Mathematics Department, Cupertino, California, USA

autor

Shiu Wai-Chee

• The Chinese University of Hong Kong, Department of Mathematics, Shatin, Hong Kong

• https://orcid.org/0000-0002-2819-8480

Bibliografia

• [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.
• [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.
• [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.
• [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.
• [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.
• [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.
• [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.
• [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.
• [12] D. Zuckerman, Linear degree extractors and the inapproximability of max clique and chromatic number, Theory Comput. 3 (2007), 103–128.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023)