On rainbow antimagic coloring and local edge antimagic coloring of graphs
Abstract
Let G be a connected graph of order n. Let f: V(G) → {1,2,...,n} be a bijection and for every uv ∈ E(G) consider wf(uv) = f(u) + f(v) as a coloring of the edge. For a pair of vertices u and v, they are connected by a rainbow path if there exists a path from u to v such that the edges have pairwise distinct colors from wf. The bijection f: V(G) → {1,2,...,n} is a rainbow antimagic coloring if for every two vertices there exists a rainbow path. Meanwhile, that bijection f: V(G) → {1,2,...,n} is local edge antimagic coloring if every two adjacent edges have distinct weights. The rainbow antimagic connection number rac(G) and local edge antimagic chromatic number χ'lea(G) is the minimum number of distinct edge weights over all rainbow antimagic coloring and local edge antimagic coloring, respectively.
We investigate the relationship between rac(G) and χ'lea(G). We prove χ'lea(G) ≤ rac(G) for all graphs and provide conditions for equality. Graphs with diameter at most 2 or satisfying rac(G) = Δ(G) achieve equality. We construct a family Ad with arbitrarily large diameter d where Δ(Ad) = χ'lea(Ad) = rac(Ad), and a family Hn = Kn,n - nK2 of diameter 3 where χ'lea(Hn) = rac(Hn) = 2n-3 > Δ(Hn). These results present hints to the full characterization of graphs G with χ'lea(G) = rac(G).
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.19184/ijc.2026.10.1.5
References
R. Adawiyah, I. I. Makhfudloh, Dafik, R. M. Prihandini and A. C. Prihandoko, On rainbow antimagic coloring of snail graph Sn, coconut root graph Crn,m, fan stalk graph Ktn and the lotus graph Lon, Barekeng: J. Math. Appl. 17(3) (2023), 1543–1552.
I. H. Agustin, M. Hasan, Dafik, R. Alfarisi and R. M. Prihandini, Local edge antimagic coloring of graphs, Far East J. Math. Sci. 102(9) (2017), 1925–1941.
L. Alam, A. Semaničová-Feňovčíková and I.-L. Popa, Graceful local antimagic labeling of graphs: A pattern analysis using python, Symmetry 17(1) (2025), 108.
P. Ananth and M. Nasre, New hardness results in rainbow connectivity, arXiv:1104.2074 (2011).
H. S. Budi, Dafik, I. M. Tirta, I. H. Agustin and A. I. Kristiana, On rainbow antimagic coloring of graphs, J. Phys.: Conf. Ser. 1832 (2021), 012016.
Y. Caro, A. Lev, Y. Roditty, Z. Tuza and R. Yuster, On rainbow connection, Electron. J. Combin. 15 (2008), #R57.
S. Chakraborty, E. Fischer, A. Matsliah and R. Yuster, Hardness and algorithms for rainbow connection, J. Comb. Optim. 21(3) (2011), 330–347.
L. S. Chandran, A. Das, D. Rajendraprasad and N. M. Varma, Rainbow connection number and connected dominating sets, J. Graph Theory 71(2) (2012), 206–218.
I. J. Chandra and D. R. Silaban, Local edge antimagic chromatic number of comb products involving path graph, Electron. J. Graph Appl. 13(1) (2025), 171–195.
G. Chartrand, G. L. Johns, K. A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133(1) (2008), 85–98.
Dafik, F. Susanto, R. Alfarisi, B. J. Septory, I. H. Agustin and M. Venkatachalam, On rainbow antimagic coloring of graphs, Adv. Math. Models Appl. 6(3) (2021), 278–291.
Dafik, R. N. Wahidah, E. R. Albirri and S. K. S. Husain, On the study of rainbow antimagic coloring of special graphs, Cauchy: J. Mat. Murni Apl. 7(4) (2023), 585–596.
J. Ekstein, P. Holub, T. Kaiser, M. Koch, S. Matos Camacho, Z. Ryjaček and I. Schiermeyer, The rainbow connection number of 2-connected graphs, Discrete Math. 313(19) (2013), 1884–1893.
J. A. Gallian, A dynamic survey of graph labelings, Electron. J. Combin. (2025), #DS6.
F. F. Hadiputra, D. R. Silaban and T. K. Maryati, Super local edge anti-magic total coloring of paths and its derivation, Indones. J. Combin. 3(2) (2020), 126–139.
F. F. Hadiputra, K. A. Sugeng, D. R. Silaban, T. K. Maryati and D. Froncek, Chromatic number of super vertex local antimagic total labelings of graphs, Electron. J. Graph Appl. 9(2) (2021), 485–498.
F. F. Hadiputra and T. K. Maryati, A note on local edge antimagic chromatic number of graphs, Proyecciones 43(2) (2024), 447–458.
N. Hartsfield and G. Ringel, Pearls in Graph Theory: A Comprehensive Introduction, revised and augmented edition, Academic Press, Boston, 1994.
M. Krivelevich and R. Yuster, The rainbow connection of a graph is (at most) reciprocal to its minimum degree, J. Graph Theory 63(3) (2010), 185–191.
J. Li, G.-C. Lau and W.-C. Shiu, On modulo local antimagic chromatic number of graphs, J. Discrete Math. Sci. Cryptogr. 25(8) (2022), 2519–2533.
X. Li and Y. Sun, Rainbow Connections of Graphs, SpringerBriefs in Mathematics (2012), Springer, New York.
X. Li, Y. Shi and Y. Sun, Rainbow connections of graphs: a survey, Graphs Combin. 29(1) (2013), 1–38.
S. Maghfiro, Dafik, A. I. Kristiana, R. Nisviasari, Slamin and I. H. Agustin, A study of the rainbow antimagic coloring of double wheel and parachute graphs, Proceedings of the 6th International Conference of Combinatorics, Graph Theory, and Network Topology (ICCGANT 2022) (2023), 120–132.
T. K. Maryati and F. F. Hadiputra, Local edge antimagic chromatic number of join product of graphs, Indones. J. Combin. 9(2) (2025), 69–77.
S. Rajkumar and M. Nalliah, On local edge antimagic chromatic number of graphs, Proyecciones 41(6) (2022), 1397–1412.
I. Schiermeyer, Rainbow connection in graphs with minimum degree three, Proceedings of IWOCA 2009, Lecture Notes in Computer Science 5874 (2009), 432–437.
B. J. Septory, M. I. Utoyo, Dafik, B. Sulistiyono and I. H. Agustin, On rainbow antimagic coloring of special graphs, J. Phys.: Conf. Ser. 1836 (2021), 012016.
B. J. Septory, L. Susilowati, Dafik, V. Lokesha and G. Nagamani, On the study of rainbow antimagic connection number of corona product of graphs, Eur. J. Pure Appl. Math. 16(1) (2023), 271–285.
B. Sulistiyono, Slamin, Dafik, I. H. Agustin and R. Alfarisi, On rainbow antimagic coloring of some graphs, J. Phys.: Conf. Ser. 1465 (2020), 012029.
Y. Walfried, I. J. Chandra and D. R. Silaban, Local edge antimagic coloring for chain of path and cycle, Indones. J. Combin. 9(1) (2025), 13–20.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.