On the Minimum Coprime Number of Some Graphs
Article Sidebar
Keywords:
-
Coprime Labeling, Disjoint Union, Dumbbell Graph, Minimum Coprime Number
Abstract
Let G be a finite simple graph. A coprime labeling of G is an injective assignment of positive integers to the vertices such that adjacent vertices receive relatively prime labels. The minimum coprime number of G, denoted by pr(G), is the smallest integer k for which G admits a coprime labeling using labels from {1, 2, ..., k}. In this paper, we determine the exact minimum coprime number of several graph families, namely the disjoint union of cycle graphs, the disjoint union of complete graphs, and dumbbell graphs. For the graph mCn with n odd, explicit coprime labeling constructions are provided and exact values of pr(mCn) are obtained for several infinite families. We also establish exact minimum coprime numbers for mKn and characterize prime and coprime labelings of dumbbell graphs according to the parity of their parameters. Furthermore, constructive labeling functions are presented for all considered graph classes. These results extend previous studies on minimum coprime labeling for graph operations and disconnected graph families.
References
Aigner, M. and E. Triesch (1994). Codings of Graphs with Binary Edge Labels. Graphs and Combinatorics, 10(1); 1–10
Ashokkumar, S. and S. Maragathavalli (2015). Prime Labeling of Some Special Graphs. IOSR Journal of Mathematics, 11(1); 1–5
Asplund, J. and N. B. Fox (2017). Minimum Coprime Labelings for Operations on Graphs. arXiv Preprint
Asplund, J. and N. B. Fox (2021). Minimum Coprime Labelings of Generalized Petersen and Prism Graphs. Journal of Integer Sequences, 24(2); 1–26
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
Chidambaraswamy, J. and R. Sitaramachandrarao (1987). On the Probability That the Values of m Polynomials Have a Given GCD. Journal of Number Theory, 26(3); 237–245
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
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. 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
Hora, A. and N. Obata (2007). Quantum Probability and Spectral Analysis of Graphs. Springer Nature, Berlin, Germany
Howson, A. G. (1972). A Handbook of Terms Used in Algebra and Analysis. Cambridge University Press, Cambridge, England
Jin, X. T. and R. K. Yeh (2005). Graph Distance-Dependent Labeling Related to Code Assignment in Computer Networks. Naval Research Logistics, 52(2); 159–164
Komarullah, H., N. Hidayat, V. H. Krisnawati, and K. Wijaya (2026a). Prime and Odd Prime Labelings of Broom Graphs and Some Related Graphs. Pan-American Journal of Mathematics, 5(9); 1–9
Komarullah, H., N. Hidayat, V. H. Krisnawati, and K. Wijaya (2026b). Prime and Odd Prime Labelings on Cycle-Related Graphs. Science and Technology Indonesia, 11(2); 551–558
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
Komarullah, H., Slamin, and K. Wijaya (2024). Pelabelan Koprima pada Amalgamasi Graf Lengkap dan Graf Berlian. Limits: Journal of Mathematics and Its Applications, 21(1); 1–12
Lau, G. C., H. H. Chu, N. Suhadak, F. Y. Foo, and H. K. Ng (2016). On SD-Prime Cordial Graphs. International Journal of Pure and Applied Mathematics, 106(4); 1017–1028
Lee, C. (2020). Minimum Coprime Graph Labelings. Journal of Integer Sequences, 23(2); 1–15
Patel, S. K. and N. P. Shrimali (2015). Neighborhood-Prime Labeling. International Journal of Mathematics and Soft Computing, 5; 135–143
Pikhurko, O. (2007). Trees are Almost Prime. Discrete Mathematics, 307(11–12); 1455–1462
Prajapati, U. M. and R. M. Gajjar (2017). Some Labeling Techniques of Braided Star Graph. International Journal of Mathematics and Its Applications, 5; 361–369
Prajapati, U. M. and S. J. Gajjar (2015). Prime Labeling of Generalized Petersen Graph. International Journal of Mathematics and Soft Computing, 5; 65–71
Prajapati, U. M. and K. P. Shah (2018). On Odd Prime Labeling. International Journal of Research and Analytical Reviews, 5(4); 284–294
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 Labeling. 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, 55(4); 259–262
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. (in Indonesia)
Tout, A. D., A. N. Dabboucy, and K. Howalla (1982). Prime Labeling of Graphs. National Academy Science Letters, 11; 365–368
Vaidya, S. K. and U. M. Prajapati (2011). Some Results on Prime and K-Prime Labeling. Journal of Mathematics Research, 3(1); 66–75
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
Wang, J., F. Belardo, Q. Huang, and E. M. L. Marzi (2010). Spectral Characterizations of Dumbbell Graphs. Electronic Journal of Combinatorics, 17; 1–16
Wijayanti, D. E., N. Hidayat, D. Indriati, A. R. 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, 9(1); 890–895
Youssef, M. Z. and E. A. Elsakhawi (2007). Some Properties of Prime Graphs. Ars Combinatoria, 84; 129–140
Ashokkumar, S. and S. Maragathavalli (2015). Prime Labeling of Some Special Graphs. IOSR Journal of Mathematics, 11(1); 1–5
Asplund, J. and N. B. Fox (2017). Minimum Coprime Labelings for Operations on Graphs. arXiv Preprint
Asplund, J. and N. B. Fox (2021). Minimum Coprime Labelings of Generalized Petersen and Prism Graphs. Journal of Integer Sequences, 24(2); 1–26
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
Chidambaraswamy, J. and R. Sitaramachandrarao (1987). On the Probability That the Values of m Polynomials Have a Given GCD. Journal of Number Theory, 26(3); 237–245
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
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. 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
Hora, A. and N. Obata (2007). Quantum Probability and Spectral Analysis of Graphs. Springer Nature, Berlin, Germany
Howson, A. G. (1972). A Handbook of Terms Used in Algebra and Analysis. Cambridge University Press, Cambridge, England
Jin, X. T. and R. K. Yeh (2005). Graph Distance-Dependent Labeling Related to Code Assignment in Computer Networks. Naval Research Logistics, 52(2); 159–164
Komarullah, H., N. Hidayat, V. H. Krisnawati, and K. Wijaya (2026a). Prime and Odd Prime Labelings of Broom Graphs and Some Related Graphs. Pan-American Journal of Mathematics, 5(9); 1–9
Komarullah, H., N. Hidayat, V. H. Krisnawati, and K. Wijaya (2026b). Prime and Odd Prime Labelings on Cycle-Related Graphs. Science and Technology Indonesia, 11(2); 551–558
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
Komarullah, H., Slamin, and K. Wijaya (2024). Pelabelan Koprima pada Amalgamasi Graf Lengkap dan Graf Berlian. Limits: Journal of Mathematics and Its Applications, 21(1); 1–12
Lau, G. C., H. H. Chu, N. Suhadak, F. Y. Foo, and H. K. Ng (2016). On SD-Prime Cordial Graphs. International Journal of Pure and Applied Mathematics, 106(4); 1017–1028
Lee, C. (2020). Minimum Coprime Graph Labelings. Journal of Integer Sequences, 23(2); 1–15
Patel, S. K. and N. P. Shrimali (2015). Neighborhood-Prime Labeling. International Journal of Mathematics and Soft Computing, 5; 135–143
Pikhurko, O. (2007). Trees are Almost Prime. Discrete Mathematics, 307(11–12); 1455–1462
Prajapati, U. M. and R. M. Gajjar (2017). Some Labeling Techniques of Braided Star Graph. International Journal of Mathematics and Its Applications, 5; 361–369
Prajapati, U. M. and S. J. Gajjar (2015). Prime Labeling of Generalized Petersen Graph. International Journal of Mathematics and Soft Computing, 5; 65–71
Prajapati, U. M. and K. P. Shah (2018). On Odd Prime Labeling. International Journal of Research and Analytical Reviews, 5(4); 284–294
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 Labeling. 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, 55(4); 259–262
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. (in Indonesia)
Tout, A. D., A. N. Dabboucy, and K. Howalla (1982). Prime Labeling of Graphs. National Academy Science Letters, 11; 365–368
Vaidya, S. K. and U. M. Prajapati (2011). Some Results on Prime and K-Prime Labeling. Journal of Mathematics Research, 3(1); 66–75
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
Wang, J., F. Belardo, Q. Huang, and E. M. L. Marzi (2010). Spectral Characterizations of Dumbbell Graphs. Electronic Journal of Combinatorics, 17; 1–16
Wijayanti, D. E., N. Hidayat, D. Indriati, A. R. 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, 9(1); 890–895
Youssef, M. Z. and E. A. Elsakhawi (2007). Some Properties of Prime Graphs. Ars Combinatoria, 84; 129–140
Authors
Komarullah, H., Wijaya, K., Hidayat, N., & Krisnawati, V. H. (2026). On the Minimum Coprime Number of Some Graphs. Science and Technology Indonesia, 11(4), 1300–1310. https://doi.org/10.26554/sti.2026.11.4.1300-1310
This work is licensed under a Creative Commons Attribution 4.0 International License.