RAINBOW CONNECTION NUMBERS IN GRAPHS: A COMPREHENSIVE STUDY - Gema Hista Medika; Syafrizal Sy; Muhafzan Muhafzan; Zulfaneti Zulfaneti (UIN Imam Bonjol Padang, 2026)
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.