Generation of anti-magic graphs from binary graph products


  • P. Ragukumar Vellore Institute of Technology.



corona product, edge corona product, rooted product, anti-magic graphs


An anti-magic labeling of a graph G is a one-to-one correspondence between E(G) and {1, 2, ··· , |E|} such that the vertex-sum for distinct vertices are different. Vertex-sum of a vertex u ∈ V (G) is the sum of labels assigned to edges incident to the vertex u. It was conjectured by Hartsfield and Ringel that every tree other than K2 has an anti-magic labeling. In this paper, we consider various binary graph products such as corona, edge corona and rooted products to generate anti-magic graphs. We prove that corona products of an anti-magic regular graph G with K1 and K2 are anti-magic. Further, we prove that rooted product of two anti-magic trees are anti-magic. Also, we prove that rooted product of an anti-magic graph with an anti-magic tree admits anti-magic labeling.

Author Biography

P. Ragukumar, Vellore Institute of Technology.

School of Advanced Sciences.


N. Alon, G. Kaplan, A. Lev, Y. Roditty and R. Yuster, “Dense graphs are antimagic”, Journal of Graph Theory, vol. 47, pp. 297-309, 2004.

T. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms. 2nd ed. MIT Press, 2001.

D. Cranston, Y. Liang and X. Zhu, “Regular graphs of odd degree are antimagic”, Journal of Graph Theory, vol. 80, no. 1, pp. 28-33, 2004.

R. Frucht and F. Harary, “On the corona of two graphs”, Aequationes mathematicae, vol. 4, pp. 322-325, 1970.

J. A. Gallian, “A Dynamic Survey of Graph Labeling”, The Electronic Journal of Combinatorics, 22nd Edition, #DS6, 2019.

C. D. Godsil and B. D. McKay, “A new graph product and its spectrum”, Bulletin of the Australasian Mathematical Society, vol. 18, no. 1, pp. 21-28, 1978.

N. Hartsfield and G. Ringel, Pearls in Graph Theory. Boston: Academic Press, 1990.

Y. Hou and W.C. Shiu, “The spectrum of the edge corona of two graphs”, Electronic Journal of Linear Algebra, vol. 20, pp. 586-594, 2010.

G. Kaplan, A. Lev and Y. Roditty, “On zero-sum partitions and anti-magic tres”, Discrete Mathematics, vol. 309, pp. 2010-2014, 2009.

Y. Liang and X. Zhu, “Antimagic labeling of cubic graphs”, Journal. Graph Theory, vol. 75, pp. 31-36, 2013.

Y. Liang, T. Wong and X. Zhu, “Anti-magic labeling of tres”, Discrete Mathematics, vol. 331, pp. 9-14, 2014.

J. Shang, “Spiders are antimagic”, Ars Combinatoria, vol. 118, pp. 367-372, 2015.

D. B. West, Introduction to Graph Theory. 2nd ed. India: Prentice Hall of India, 2001.



How to Cite

P. Ragukumar, “Generation of anti-magic graphs from binary graph products”, Proyecciones (Antofagasta, On line), vol. 42, no. 3, pp. 651-661, May 2023.