Some Results on Relatively Prime Edge Labeled Graph




Prime graph, Coprime graph, Relatively prime edge labeled graph, Relatively prime index


Prime labeling and relatively prime edge labeling have the same idea for labeling the general graph \(G\). Prime labeling labels the vertices of the general graph in such a way that adjacent vertices receive relatively prime labels. Similarly, relatively prime edge labeling, labels the edges in a way that the adjacent edges have relatively prime labels. Also, there are graphs that do not have relatively prime edge labeling. Hence the concept of relatively prime index is introduced, which finds the minimum number of edges to be removed from \(G\) to make it a relatively prime edge labeled graph. The main purpose of the current study is to discuss some results on the topic of relatively prime edge labeled graphs and relatively prime index.


Download data is not yet available.


J. Asplund and N. B. Fox, Minimum coprime labelings for operations on graphs, Integers 19 (2019), Article number: A24, 26 pages, URL:

H.-L. Fu and K.-C. Huang, On prime labellings, Discrete Mathematics 127(1-3) (1994), 181 – 186, DOI: 10.1016/0012-365X(92)00477-9.

J. A. Gallian, A dynamic survey of graph labelling (Graph labelling), The Electronic Journal of Combinatorics DS6 (Version 25) (2022), 623 pages, DOI: 10.37236/27.

R. Jagadesh and J. B. Babujee, On edge vertex prime labeling, International Journal of Pure and Applied Mathematics 114(6) (2017), 209 – 218, URL:

R. Janani and T. Ramachandran, On relatively prime edge labeling of graphs, Engineering Letters 30(2) (2022), 659 – 665, URL:

A. V. Kanetkar, Prime labeling of grids, AKCE International Journal of Graphs and Combinatorics 6(1) (2009), 135 – 142, URL:

G. C. Lau and W. C. Shiu, On SD-prime labeling of graphs, Utilitas Mathematica 106 (2018), 149 – 164, URL:

M. H. B. A. Mostafa and E. Ghorbani, Hamiltonicity of a coprime graph, Graphs and Combinatorics 37(6) (2021), 2387 – 2395, DOI: 10.1007/s00373-021-02362-1.

A. Rosa, On certain valuations of the vertices of a graph, in: Theory of Graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach, N.Y. and Dunod, Paris (1967), pp. 349 – 355.

W.-C. Shiua, G.-C. Laub and S.-M. Leec, On (semi-) edge-primality of graphs, Iranian Journal of Mathematical Sciences and Informatics 12(2) (2017), 1 – 14, DOI: 10.7508/ijmsi.2017.2.001.

A. Tout, A. N. Dabboucy and K. Howalla, Prime labeling of graphs, National Academy Science Letters 11 (1982), 365 – 368.

S. K. Vaidya and U. M. Prajapati, Some results on prime and k-prime labeling, Journal of Mathematics Research 3(1) (2011), 66 – 75, DOI: 10.5539/jmr.v3n1p66.




How to Cite

Janani, R., & Ramachandran, T. (2024). Some Results on Relatively Prime Edge Labeled Graph. Communications in Mathematics and Applications, 14(5), 1565–1573.



Research Article