On Prime Index of a Graph

Janani R, Ramachandran T


In prime labeling, vertices are labeled from 1 to n, with the condition that any two adjacent vertices have relatively prime labels. Coprime labeling maintains the same criterion as prime labeling with adjacent vertices using any set of distinct positive integers. Minimum coprime number prG, is the minimum value k for which G has coprime labeling. There are many graphs that do not possess prime labeling, and hence have coprime labeling. The primary purpose of this work is to change a coprime labeled graph into a prime graph by removing the minimum number of edges. Thus, the prime index ε(G) is the least number of edges to be removed from a coprime graph G to form a prime graph. In this study, the prime index of various graphs is determined. Also, an algorithmic way to determine the prime index of the complete graph is found.


Prime labeling, Coprime labeling, Minimum Coprime Number, Prime index

Full Text:



Jameson, G.J.O. (2003), The Prime number theorem, Cambridge University Press, Cambridge.

Tout, R., Dabboucy, A.N., Howalla, K.(1982), Prime labeling of graphs, National Academy Science Letters-India, 5(11), pp. 365–368.

Fu, H.L., Huang, K.C.(1994), On prime labellings, Discrete Mathematics, 127, pp. 181–186.

Janani, R., Ramachandran, T.(2022), On Relatively Prime Edge Labeling of Graphs, Engineering Letters, 30(2), pp. 659–665.

Berliner, A. H. et al., (2016), Coprime and prime labelings of graphs, Journal of Integer Sequences,19(5), pp. 1–14.

Gallian, J.A., (2002), A dynamic survey of graph labeling, In The Electronic Journal of Combinatorics.

Asplund,J and Bradley Fox.N., (2017), Minimum Coprime Labelings for Operations on Graphs, Integers, pp. 1–19.

Lee, C., (2019). Minimum coprime graph labelings. arXiv preprint arXiv:1907.12670.

Coxeter, H. et al. (1950), Self-dual configurations and regular graphs, Bull. Amer. Math. Soc 56, pp. 413–455.

Watkins, M. E. (1969), A theorem on Tait colorings with an application to the generalized Petersen graphs, J. Comb. Theory 6(2), pp. 152–164.

Bondy, J.A. Murty, U.S.R., (1976) , Graph theory with applications, 290, London: Macmillan, London.

Harary,F.(1998), Graph Theory, Narosa Publishing House, New Delhi.

Prajapati, U. M., S. J. Gajjar.,(2015), Prime labeling of generalized Petersen graph, Internat. J. Math. and Soft Comput 5, pp. 65-71.

Fu, Hung-Lin, Kuo-Ching Huang., (1994), On prime labellings, Discrete Mathematics 127, pp.181-186.

Nagoji Rao, Suryaprakash.,(2006), Graceful and Prime Labelings–Algorithms, Embeddings and Conjectures. arXiv e-prints (2020): arXiv-2006.

Ying-Ying Tan, Yi-Zheng Fan., (2010), The vertex (edge) independence number, vertex (edge) cover number and the least eigenvalue of a graph, Linear Algebra and its Applications,433(4), pp. 790-795.

DOI: http://dx.doi.org/10.23755/rm.v48i0.1315


  • There are currently no refbacks.

Copyright (c) 2023 Janani R and Ramachandran T

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Ratio Mathematica - Journal of Mathematics, Statistics, and Applications. ISSN 1592-7415; e-ISSN 2282-8214.