Progress on rainbow connection
Ingo Schiermeyer · Cologne Twente Workshop on Graphs and Combinatorial Optimization · 2010
1 IntroductionWe use [1] for terminology and notation not de ned here and consider niteand simple graphs only.An edge-coloured graph Gis called rainbow-connected if any two vertices areconnected by a path whose edges have di erent colours. This concept of rain-bow connection in graphs was recently introduced by Chartrand et al. in [4].The rainbow connection number of a connected graph G;denoted rc(G);isthe smallest number of colours that are needed in order to make Grainbowconnected. An easy observation is that if Ghas nvertices then rc(G) n 1;since one may colour the edges of a given spanning tree of Gwith di erentcolours, and colour the remaining edges with one of the already used colours.Chartrand et al. computed the precise rainbow connection number of severalgraph classes including complete multipartite graphs [4]. The rainbow connec-tion number has been studied for further graph classes in [3] and for graphswith xed minimum degree in ([3], [7], [9]).Rainbow connection has an interesting application for the secure transfer ofclassi ed information between agencies (cf. [5]). While the information needsto be protected since it relates to national security, there must also be proce-dures that permit access between appropriate parties. This two-fold issue canbe addressed by assigning information transfer paths between agencies whichmay have other agencies as intermediaries while requiring a large enough num-ber of passwords and rewalls that is prohibitive to intruders, yet small enoughto manage (that is, enough so that one or more paths between every pair ofagencies have no password repeated). An immediate question arises: Whatis the minimum number of passwords or rewalls needed that allows one or