New Families of Prime Graphs via Vertex Expansions

Ramesh R. Kanzariya; Mehul P. Rupani

doi:https://doi.org/10.14445/22315373/IJMTT-V72I6P107

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 72 | Issue 6 | Year 2026 | Article Id. IJMTT-V72I6P107 | DOI : https://doi.org/10.14445/22315373/IJMTT-V72I6P107

New Families of Prime Graphs via Vertex Expansions

Ramesh R. Kanzariya, Mehul P. Rupani

Received	Revised	Accepted	Published
26 Apr 2026	30 May 2026	19 Jun 2026	30 Jun 2026

Citation :

Ramesh R. Kanzariya, Mehul P. Rupani, "New Families of Prime Graphs via Vertex Expansions," International Journal of Mathematics Trends and Technology (IJMTT), vol. 72, no. 6, pp. 59-70, 2026. Crossref, https://doi.org/10.14445/22315373/IJMTT-V72I6P107

Abstract

In graph labeling, ‘prime labeling’ is a process where the 𝑛 vertices of a graph are assigned distinct integers from 1 to 𝑛 such that the labels of any two adjacent vertices are relatively prime. The study of prime labeling for graphs obtained through structural operations has attracted considerable attention in recent years. In this paper, we investigate the existence of prime labeling for certain classes of graphs arising from vertex expansions. Specifically, we prove that the graphs obtained by expanding the intermediate vertices of a jewel graph without prime edge and the pendent vertices of a jellyfish graph without prime edge into paths admit prime labeling. Furthermore, we establish the existence of prime labeling for zigzag graphs. These results extend the family of known prime graphs and significantly contribute to the study of prime labeling under graph expansion operations.

Keywords

Prime Labeling, Graph Expansion, Jewel Graph, Jellyfish Graph, Zigzag Graph.

References

[1] P.Z. Akbari, V.J. Kaneria, and N.A. Parmar, “Absolute Mean Graceful Labeling of Jewel Graph and Jelly Fish Graph,” International Journal of Mathematics Trends and Technology, vol. 68, no. 1, pp. 86-93, 2022.
[CrossRef] [Google Scholar] [Publisher Link]

[2] David M. Burton, Elementary Number Theory, 7^th ed., McGraw Hill, 2010.
[Google Scholar] [Publisher Link]

[3] M.K. Karthik Chidambaram, On Prime Labeling of some Special Graphs, International Journal of Food and Nutritional Sciences, vol. 11, no. 11, pp. 2068-2073, 2022. [Online]. Available: https://www.ijfans.org/uploads/paper/b216638d1f6b6bdc9d9cba3ce4cd8d93.pdf

[4] Joseph A. Gallian, “A Dynamic Survey of Graph Labeling,” The Electronic Journal of Combinatorics, vol. 28, 2018.
[Google Scholar] [Publisher Link]

[5] Jonathan L. Gross, and Jay Yellen, Graph Theory and its Applications, 2^nd ed., Chapman and Hall/CRC, 2005.
[CrossRef] [Google Scholar] [Publisher Link]

[6] Ankur Kansagara, Sanjaykumar Patel, and Jayeshbhai Vasava, “Prime Labeling in the Context of Subdivision of some Cycle Related Graphs,” TWMS Journal of Applied and Engineering Mathematics, vol. 11, no. 2, pp. 524-540, 2021.
[Google Scholar]

[7] S.K. Patel, and A.N. Kansagara, “Prime Labeling of Union Graphs,” International Journal of Scientific Research in Mathematical and Statistical Sciences, vol. 6, no. 1, pp. 86-93, 2019.
[Google Scholar] [Publisher Link]

[8] Srinivasa Ramanujan , “A Proof of Bertrand’s Postulate,” Journal of the Indian Mathematical Society, vol. 11, pp. 181-182, 1919.
[Google Scholar]

[9] A.N. Dabboucy A.D.A.N. Tout, and K. Howalla, “Prime Labeling of Graphs,” National Academy Science Letters, vol. 11, pp. 365-368, 1982.
[Google Scholar]

[10] Douglas Brent West, Introduction to Graph Theory, Prentice Hall, vol. 2, 2001.
[Google Scholar]