On Prime Index of a Graph

Authors

  • Janani R SSM Institute of Engineering and Technology, Dindigul, India
  • Ramachandran T Head, Department of Mathematics, MVM Government Arts College for Women, Dindigul, India

DOI:

https://doi.org/10.23755/rm.v48i0.1315

Keywords:

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

Abstract

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.

References

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.

Downloads

Published

2023-12-30

Issue

Vol. 48 (2023)

Section

Volume 48-2023

License

This journal provides immediate open access to its content on the principle that making research freely available to the public supports a greater global exchange of knowledge. The journal is committed to real and immediate open access for academic work. All of the journal articles are free to access immediately from the date of publication. There are no charge for readers to download articles and reviews for their own scholarly use. Benefits of open access for authors, include:

  • Free access for all users worldwide
  • Increased visibility and readership
  • Rapid publication
  • No spatial constraints
  • Authors can share their research papers on their personal web-pages (i.e. ResearchGate, etc.)

Ratio Mathematica publishes open access articles under the terms of the Creative Commons Attribution (CC BY) License. The Creative Commons Attribution License (CC-BY) allows users to copy, distribute and transmit an article, adapt the article and make commercial use of the article. The CC BY license permits commercial and non-commercial re-use of an open access article, as long as the author is properly attributed. Copyright on any research article published by Ratio Mathematica is retained by the author(s). Authors grant Ratio Mathematica a license to publish the article and identify itself as the original publisher. Authors also grant any third party the right to use the article freely as long as its original authors, citation details and publisher are identified. 
For further information visit: https://creativecommons.org/licenses/by/3.0/. The following logo will appear in any paper that will be published from the volume number 31/2016 onwards.