Prime and Odd Prime Labelings on Cycle-Related Graphs
Article Sidebar
Keywords:
-
Cycle-Related Graph, Odd Prime Graph, Relatively Prime
Abstract
Graph labeling is the process of determining integer values for vertices, edges, or both, based on certain criteria. Let G be a simple graph with the finite vertex set V(G). Prime labeling of G is a bijection ⍺:V(G)→{1,2,…,|V(G)|} for which each pair of adjacent vertices exhibits relatively prime labels. This concept has been extended to odd prime labeling, defined as a bijection ⍺:V(G)→ {1,3,...,2|V(G)|-1} satisfying the condition that the labels assigned to adjacent vertices are relatively prime labels. A graph that displays a (odd) prime labeling is designated as a (odd) prime graph. A recent conjecture state that every prime graph is an odd prime graph. In the present study, we conduct an investigation concerning prime and odd prime labeling, focusing on a range of cycle-related graphs classes. Our methods include the axiomatic descriptive approach and pattern detection techniques. We show that volcano graphs, C_3 ⨀_(x_1 y_0 ) F_n, C_3⊚K ̅_n, tadpole graphs, palm trees, and C_l ⨀_(x_1 y_0 ) mP_(n+1) are all both prime and odd prime graphs.
References
Ashokkumar, S. and S. Maragathavalli (2015). Prime Labeling of Some Special Graphs. IOSR Journal of Mathematics, 11(1); 1–5
Bača, M., Z. Kimáková, M. Lascsáková, and A. Semaničová Feňovčíková (2021). The Irregularity and Modular Irregularity Strength of Fan Graphs. Symmetry, 13(4); 605
Berliner, A. H., J. Hook, A. Mbirika, N. Dean, A. Marr, and C. D. McBee (2016). Coprime and Prime Labelings of Graphs. Journal of Integer Sequences, 19(8); 1–14
Borowiecka-Olszewska, M. and M. Hałuszczak (2013). On Ramsey (K1,m, G)-Minimal Graphs. Discrete Mathematics, 313(19); 1843–1855
Carter, H. and N. B. Fox (2022). Odd Prime Graph Labelings. arXiv preprint
Dafik, R. N. Wahidah, E. R. Albirri, and S. K. S. Husain (2023). On the Study of Rainbow Antimagic Coloring of Special Graphs. CAUCHY: Jurnal Matematika Murni dan Aplikasi, 7(4); 585–596
DeMaio, J. and J. Jacobson (2014). Fibonacci Number of the Tadpole Graph. Electronic Journal of Graph Theory and Applications, 2(2); 129–138
Deretsky, T., S. M. Lee, and J. Mitchem (1991). On Vertex Prime Labelings of Graphs. In Graph Theory, Combinatorics and Applications, volume 1. pages 359–369
Diestel, R. (2025). Graph Theory. Springer Nature, Berlin, Germany
Frucht, R. and F. Harary (1970). On the Corona of Two Graphs. Aequationes Mathematicae, 4(3); 322–325
Gallian, J. A. (2024). A Dynamic Survey of Graph Labeling. Electronic Journal of Combinatorics, 6(25); 1–712
Ganesan, R., A. Bhaalamurugan, and Christy (2019). Prime Labeling for Some New Classes of Graphs. IJRAR– International Journal of Research and Analytical Reviews, 6(2); 232–235
Ghorbani, E. and S. Kamali (2016). Prime Labeling of Ladders. arXiv preprint
Griggs, J. R. and R. K. Yeh (1992). Labelling Graphs with a Condition at Distance 2. SIAM Journal on Discrete Mathematics, 5(4); 586–595
Janani, R. and T. Ramachandran (2022). On Relatively Prime Edge Labeling of Graphs. Engineering Letters, 30(2); 659–665
Komarullah, H., Slamin, and K. Wijaya (2022). A Minimum Coprime Number for Amalgamation of Wheel. In Proceedings of the International Conference on Mathematics, Geometry, Statistics, and Computation (IC-MaGeStiC 2021). pages 53–57
Kumar, A. and A. K. Vats (2020). Application of Graph Labeling in Crystallography. Materials Today: Proceedings
Lee, S. M., I. Wui, and J. Yeh (1988). On the Amalgamation of Prime Graphs. Bulletin of the Malaysian Mathematical Society (Second Series), 11; 59–67
Meena, S. and G. Gajalakshmi (2022). Odd Prime Labeling of Graphs Related to Circular Ladder. Communications in Mathematics and Applications, 13(4); 1307–1315
Mujib, A. (2019). Bilangan Kromatik Permainan Graf Pot Bunga (Cm Sn) dan Graf Pohon Palem (Ck Pl Sm). TEOREMA: Teori dan Riset Matematika, 4(1); 13–22 (in Indonesia)
Pikhurko, O. (2007). Trees Are Almost Prime. Discrete Mathematics, 307(11–12); 1455–1462
Prajapati, U. and K. P. Shah (2018). On Odd Prime Labeling. International Journal of Research and Analytical Reviews, 5(4); 284–294
Prajapati, U. M. and S. J. Gajjar (2015). Prime Labeling of Generalized Petersen Graph. International Journal of Mathematics and Soft Computing, 5; 65–71
Prasanna, N. L., K. Sravanthi, and N. Sudhakar (2014). Applications of Graph Labeling in Communication Networks. Oriental Journal of Computer Science and Technology, 7(1); 139–145
Prihandoko, A. C., Dafik, and I. H. Agustin (2019). Implementation of Super H-Antimagic Total Graph on Establishing Stream Cipher. Indonesian Journal of Combinatorics, 3(1); 14–23
Rao, S. N. (2002). Prime Labelling. In Proceedings of the RC Bose Centenary Symposium on Discrete Mathematics and Applications. Kolkata, India
Robertson, L. and B. Small (2009). On Newman’s Conjecture and Prime Trees. Integers, 9(2); 117–128
Samuel, A. E. and S. Kalaivani (2018). Prime Labeling to Brush Graphs. International Journal of Mathematics Trends and Technology (IJMTT), 55(4); 259–262
Saraswati, E. T., D. D. Saputri, and W. W. Raharjo (2025). Enhanced Performance of Epoxy Resin–Polyimide Hybrid Composites with Aminated Carbon Nanofibers Filler. Science and Technology Indonesia, 10(1); 152–164
Seoud, M. A., A. T. Diab, and E. A. Elsahawi (1998). On Strongly-C Harmonious, Relatively Prime, Odd Graceful and Cordial Graphs. In Proceedings of the Mathematical and Physical Society of Egypt, volume 73. pages 33–55
Seoud, M. A. and M. Z. Youssef (1999). On Prime Labeling of Graphs. Congressus Numerantium, 141; 203–215
Sukirman (2016). Teori Bilangan. Universitas Terbuka, Tangerang Selatan. (In Indonesian)
Tout, A., A. N. Dabboucy, and K. Howalla (1982). Prime Labeling of Graphs. National Academy Science Letters, 11; 365–368
Vinutha, M. S. and P. Arathi (2017). Applications of Graph Coloring and Labeling in Computer Science. International Journal on Future Revolution in Computer Science and Communication Engineering, 3(8); 14–16
Wijayanti, E. D., N. Hidayat, D. Indriati, R. A. Alghofari, and Slamin (2023). On Distance Vertex Irregular Total k-Labeling. Science and Technology Indonesia, 8(3); 479–485
Wilson, L. K. and H. Jini (2021). Prime Labeling of Torch Graph. Malaya Journal of Matematik (MJM), 9(1); 890–895
Youssef, M. and Z. Almoreed (2020). On Odd Prime Labeling of Graphs. Open Journal of Discrete Applied Mathematics (ODAM), 3(3); 33–40
Youssef, M. Z. and E. A. Elsakhawi (2007). Some Properties of Prime Graphs. Ars Combinatoria, 84; 129–140
Bača, M., Z. Kimáková, M. Lascsáková, and A. Semaničová Feňovčíková (2021). The Irregularity and Modular Irregularity Strength of Fan Graphs. Symmetry, 13(4); 605
Berliner, A. H., J. Hook, A. Mbirika, N. Dean, A. Marr, and C. D. McBee (2016). Coprime and Prime Labelings of Graphs. Journal of Integer Sequences, 19(8); 1–14
Borowiecka-Olszewska, M. and M. Hałuszczak (2013). On Ramsey (K1,m, G)-Minimal Graphs. Discrete Mathematics, 313(19); 1843–1855
Carter, H. and N. B. Fox (2022). Odd Prime Graph Labelings. arXiv preprint
Dafik, R. N. Wahidah, E. R. Albirri, and S. K. S. Husain (2023). On the Study of Rainbow Antimagic Coloring of Special Graphs. CAUCHY: Jurnal Matematika Murni dan Aplikasi, 7(4); 585–596
DeMaio, J. and J. Jacobson (2014). Fibonacci Number of the Tadpole Graph. Electronic Journal of Graph Theory and Applications, 2(2); 129–138
Deretsky, T., S. M. Lee, and J. Mitchem (1991). On Vertex Prime Labelings of Graphs. In Graph Theory, Combinatorics and Applications, volume 1. pages 359–369
Diestel, R. (2025). Graph Theory. Springer Nature, Berlin, Germany
Frucht, R. and F. Harary (1970). On the Corona of Two Graphs. Aequationes Mathematicae, 4(3); 322–325
Gallian, J. A. (2024). A Dynamic Survey of Graph Labeling. Electronic Journal of Combinatorics, 6(25); 1–712
Ganesan, R., A. Bhaalamurugan, and Christy (2019). Prime Labeling for Some New Classes of Graphs. IJRAR– International Journal of Research and Analytical Reviews, 6(2); 232–235
Ghorbani, E. and S. Kamali (2016). Prime Labeling of Ladders. arXiv preprint
Griggs, J. R. and R. K. Yeh (1992). Labelling Graphs with a Condition at Distance 2. SIAM Journal on Discrete Mathematics, 5(4); 586–595
Janani, R. and T. Ramachandran (2022). On Relatively Prime Edge Labeling of Graphs. Engineering Letters, 30(2); 659–665
Komarullah, H., Slamin, and K. Wijaya (2022). A Minimum Coprime Number for Amalgamation of Wheel. In Proceedings of the International Conference on Mathematics, Geometry, Statistics, and Computation (IC-MaGeStiC 2021). pages 53–57
Kumar, A. and A. K. Vats (2020). Application of Graph Labeling in Crystallography. Materials Today: Proceedings
Lee, S. M., I. Wui, and J. Yeh (1988). On the Amalgamation of Prime Graphs. Bulletin of the Malaysian Mathematical Society (Second Series), 11; 59–67
Meena, S. and G. Gajalakshmi (2022). Odd Prime Labeling of Graphs Related to Circular Ladder. Communications in Mathematics and Applications, 13(4); 1307–1315
Mujib, A. (2019). Bilangan Kromatik Permainan Graf Pot Bunga (Cm Sn) dan Graf Pohon Palem (Ck Pl Sm). TEOREMA: Teori dan Riset Matematika, 4(1); 13–22 (in Indonesia)
Pikhurko, O. (2007). Trees Are Almost Prime. Discrete Mathematics, 307(11–12); 1455–1462
Prajapati, U. and K. P. Shah (2018). On Odd Prime Labeling. International Journal of Research and Analytical Reviews, 5(4); 284–294
Prajapati, U. M. and S. J. Gajjar (2015). Prime Labeling of Generalized Petersen Graph. International Journal of Mathematics and Soft Computing, 5; 65–71
Prasanna, N. L., K. Sravanthi, and N. Sudhakar (2014). Applications of Graph Labeling in Communication Networks. Oriental Journal of Computer Science and Technology, 7(1); 139–145
Prihandoko, A. C., Dafik, and I. H. Agustin (2019). Implementation of Super H-Antimagic Total Graph on Establishing Stream Cipher. Indonesian Journal of Combinatorics, 3(1); 14–23
Rao, S. N. (2002). Prime Labelling. In Proceedings of the RC Bose Centenary Symposium on Discrete Mathematics and Applications. Kolkata, India
Robertson, L. and B. Small (2009). On Newman’s Conjecture and Prime Trees. Integers, 9(2); 117–128
Samuel, A. E. and S. Kalaivani (2018). Prime Labeling to Brush Graphs. International Journal of Mathematics Trends and Technology (IJMTT), 55(4); 259–262
Saraswati, E. T., D. D. Saputri, and W. W. Raharjo (2025). Enhanced Performance of Epoxy Resin–Polyimide Hybrid Composites with Aminated Carbon Nanofibers Filler. Science and Technology Indonesia, 10(1); 152–164
Seoud, M. A., A. T. Diab, and E. A. Elsahawi (1998). On Strongly-C Harmonious, Relatively Prime, Odd Graceful and Cordial Graphs. In Proceedings of the Mathematical and Physical Society of Egypt, volume 73. pages 33–55
Seoud, M. A. and M. Z. Youssef (1999). On Prime Labeling of Graphs. Congressus Numerantium, 141; 203–215
Sukirman (2016). Teori Bilangan. Universitas Terbuka, Tangerang Selatan. (In Indonesian)
Tout, A., A. N. Dabboucy, and K. Howalla (1982). Prime Labeling of Graphs. National Academy Science Letters, 11; 365–368
Vinutha, M. S. and P. Arathi (2017). Applications of Graph Coloring and Labeling in Computer Science. International Journal on Future Revolution in Computer Science and Communication Engineering, 3(8); 14–16
Wijayanti, E. D., N. Hidayat, D. Indriati, R. A. Alghofari, and Slamin (2023). On Distance Vertex Irregular Total k-Labeling. Science and Technology Indonesia, 8(3); 479–485
Wilson, L. K. and H. Jini (2021). Prime Labeling of Torch Graph. Malaya Journal of Matematik (MJM), 9(1); 890–895
Youssef, M. and Z. Almoreed (2020). On Odd Prime Labeling of Graphs. Open Journal of Discrete Applied Mathematics (ODAM), 3(3); 33–40
Youssef, M. Z. and E. A. Elsakhawi (2007). Some Properties of Prime Graphs. Ars Combinatoria, 84; 129–140
Authors
Komarullah, H., Hidayat, N., Krisnawati, V. H., & Wijaya, K. (2026). Prime and Odd Prime Labelings on Cycle-Related Graphs. Science and Technology Indonesia, 11(2), 551–558. https://doi.org/10.26554/sti.2026.11.2.551-558
This work is licensed under a Creative Commons Attribution 4.0 International License.