RAINBOW CONNECTION NUMBERS IN GRAPHS: A COMPREHENSIVE STUDY

Gema Hista Medika, Syafrizal Sy, Muhafzan Muhafzan, Zulfaneti Zulfaneti

Abstract


The rainbow connection number is a graph parameter that integrates edge colouring and graph connectivity. A connected graph is said to be rainbow connected if every pair of vertices is joined by a path whose edges have distinct colours, and the rainbow connection number represents the minimum number of colours required to satisfy this property. This study aims to provide a comprehensive and systematic analysis of research developments related to rainbow connection numbers in graphs. The method employed is a systematic literature review of reputable international journals and nationally accredited publications. The analysis covers fundamental definitions, known values for various classes of graphs, relationships with structural parameters such as diameter, minimum degree, and connectivity, as well as computational complexity and several important variants, including strong rainbow connection, rainbow vertex-connection, and total rainbow connection. The results indicate that the rainbow connection number is strongly influenced by graph structure, with diameter serving as a natural lower bound and connectivity contributing to tighter upper bounds. Furthermore, determining the exact value for general graphs is computationally intractable, motivating the use of approximation and heuristic approaches. This study also identifies research gaps, particularly in algorithmic development and the analysis of complex graph class, and highlights potential applications in communication networks and network security.

Keywords


Graph Theory; Rainbow Connection Number; Edge Coloring; Graph Connectivity

Full Text:

PDF

References


Asmara, A. (2018). Bilangan Rainbow Connection pada Graf Jahangir. Jurnal Matematika, 8(2), 75–82.

Basavaraju, M., Chandran, L. S., Rajendraprasad, D., & Ramaswamy, S. (2012). Rainbow Connection Number of Graph Powers and Products. Journal of Combinatorial Optimization, 24(4), 563–578. https://doi.org/10.1007/s10878-011-9430-8

Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory with Applications. Springer.

Chakraborty, S., Fischer, E., Matsliah, A., & Yuster, R. (2009). Hardness and Algorithms for Rainbow Connectivity. Journal of Combinatorial Optimization, 21(3), 330–347. https://doi.org/10.1007/s10878-009-9250-0

Chartrand, Johns, G. ., McKeon, K. ., & P.Zhang. (2008). Rainbow Connection in Graphs. Math Bohemica.

Chen, G., Li, X., & Yao, Y. (2014). Algorithmic Aspects of Rainbow Connectivity. Theoretical Computer Science, 555, 1–8. https://doi.org/10.1016/j.tcs.2014.07.029

Chen, L., Li, X., & Liu, W. (2018). Rainbow Connection and Its Variants: A Survey. Journal of Combinatorial Optimization, 35(3), 707–727. https://doi.org/10.1007/s10878-017-0179-4

Diestel, R. (2017). Graph Theory (5th ed.). Springer.

Doan, T. H., & Schiermeyer, I. (2018). On the Strong Rainbow Connection of Graphs. Discrete Mathematics & Theoretical Computer Science, 20(2), 1–12.

Ekstein, J., Holub, P., Kaiser, T., Koch, M., Ryjacek, Z., & Schiermeyer, I. (2012). The Rainbow Connection Number of 2-Connected Graphs. Discussiones Mathematicae Graph Theory, 32(4), 659–668.

Estetikasari, D., & Sy, S. (2013). On the Rainbow Connection for Some Corona Graphs. 7(100), 4975–4980.

Holliday, R., Magnant, C., & Nowbandegani, P. S. (2014). Note on Rainbow Connection in Oriented Graphs with Diameter 2. Theory and Applications of Graphs, 1(1).

Krivelevich, M., & Yuster, R. (2010). The Rainbow Connection of a Graph Is (at Most) Reciprocal to Its Minimum Degree. Journal of Graph Theory, 63(3), 185–191. https://doi.org/10.1002/jgt.20418

Lakisa, Y., Lestari, D., & Talib, M. (2022). Rainbow Connection Number of Ferris Wheel Graphs. Jurnal Matematika Dan Aplikasinya, 21(1), 45–54.

Li, H., Li, X., & Liu, S. (2012). Rainbow Connection of Graphs with Diameter 2. Discrete Mathematics. https://doi.org/10.1016/j.disc.2012.01.009

Li, X. (2017). Rainbow Connection in Graphs: A Survey. Springer.

Li, X., Liu, S., Chandran, L. S., Mathew, R., & Rajendraprasad, D. (2012). Rainbow Connection Number and Connectivity. Electronic Journal of Combinatorics, 19(1).

Li, X., & Magnant, C. (2015). Rainbow Vertex-Connection. Discrete Applied Mathematics, 193, 92–100. https://doi.org/10.1016/j.dam.2014.10.023

Li, X., Shi, Y., Zhang, L., & Sun, Y. (2014). Total Rainbow k-Connection in Graphs. Discrete Applied Mathematics, 174, 92–101. https://doi.org/10.1016/j.dam.2014.04.012

Li, X., & Sun, Y. (2011). A Survey on Rainbow Connection of Graphs. ArXiv Preprint ArXiv:1101.5747.

Li, X., & Sun, Y. (2012). Rainbow Connections of Graphs. Springer. https://doi.org/10.1007/978-1-4614-3118-0

Makhfduloh, I. I., Dafik, D., & Adawiyah, R. (2023). Rainbow Connection pada Graf Siput, Graf Tunas Kelapa dan Graf Lotus. CGANT Journal of …. http://jcgantunej.or.id/index.php/cgant/article/view/91

Medika, G. H. (2013). Rainbow Connection Pada Beberapa Graf. Jurnal Matematika UNAND, 2(2), 17. https://doi.org/10.25077/jmu.2.2.17-25.2013

Medika, G. H., & Sy, S. (2025). The Rainbow Connection Number of Snail Graphs. 4–9.

Medika, G. H., Tomi, Z. B., & Wulan, E. R. (2024). Bilangan rainbow connection pada graf buku. KUBIK: Jurnal Publikasi Ilmiah Matematika, 9(1), 87–97.

Noor, C. A. P., Yahya, L., Nasib, S. K., & Yahya, N. I. (2021). BILANGAN TERHUBUNG PELANGI PADA GRAF SALJU (Sn_m). Journal of Fundamental Mathematics and Applications (JFMA), 4(1), 29–44. https://doi.org/10.14710/jfma.v4i1.9035

Schiermeyer, I. (2009). Rainbow Connection in Graphs with Minimum Degree Three. In Lecture Notes in Computer Science (Vol. 5874, pp. 432–437). Springer.

Schiermeyer, I. (2011). Bounds for the Rainbow Connection Number of Graphs. Discussiones Mathematicae Graph Theory, 31(2), 387–395.

Suthar, B., Parmar, D., Patel, D., Sharma, S., & Modi, Y. (2021). Rainbow Connection Number Of Some Graphs. Webology, 41(3), 809–826. https://doi.org/10.7151/dmgt.2326

Sy, S., Medika, G. H., & Yulianti, L. (2013). The Rainbow Connection of Fan and Sun. Applied Mathematical Sciences, 7(64), 3155–3160.

West, D. B. (2021). Introduction to Graph Theory (3rd ed.). Pearson.




DOI: https://doi.org/10.15548/mej.v10i1.13681

Refbacks

  • There are currently no refbacks.


Copyright (c) 2026 Author

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

Sinta 2
Accredited Sinta 2 Starting from Vol. 8 No. 2 (2024) until Vol. 13 No. 1 (2029)
Math Educa Journal
Mathematics Education Department | FTK UIN Imam Bonjol Padang

Jl. Prof. Mahmud Yunus Lubuk Lintah, Anduring, Kec. Kuranji, Kota Padang, Sumatera Barat 25153

Email: [email protected]
p-ISSN: 2580-6726 | e-ISSN: 2598-2133