Generation of anti-magic graphs from binary graph products
DOI:
https://doi.org/10.22199/issn.0717-6279-5220Keywords:
corona product, edge corona product, rooted product, anti-magic graphsAbstract
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.
References
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. https://doi.org/10.1002/jgt.20027
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. https://doi.org/10.1002/jgt.21836
R. Frucht and F. Harary, “On the corona of two graphs”, Aequationes mathematicae, vol. 4, pp. 322-325, 1970. https://doi.org/10.1007/BF01844162
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. https://doi.org/10.1017/S0004972700007760
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. https://doi.org/10.13001/1081-3810.1395
G. Kaplan, A. Lev and Y. Roditty, “On zero-sum partitions and anti-magic tres”, Discrete Mathematics, vol. 309, pp. 2010-2014, 2009. https://doi.org/10.1016/j.disc.2008.04.012
Y. Liang and X. Zhu, “Antimagic labeling of cubic graphs”, Journal. Graph Theory, vol. 75, pp. 31-36, 2013. https://doi.org/10.1002/jgt.21718
Y. Liang, T. Wong and X. Zhu, “Anti-magic labeling of tres”, Discrete Mathematics, vol. 331, pp. 9-14, 2014. https://doi.org/10.1016/j.disc.2014.04.021
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.
Published
How to Cite
Issue
Section
Copyright (c) 2023 P. Ragukumar
This work is licensed under a Creative Commons Attribution 4.0 International License.
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
