The concept of rainbow colouring was introduced in [1]}. It was shown in [2]} that computing the rainbow connection number of a graph is NP-Hard. To rainbow colour a graph, it is enough to ensure that every edge of some spanning tree in the graph gets a distinct colour. Hence the order of the graph minus one is an upper bound for its rainbow connection number. Many authors view rainbow connectivity as one `quantifiable' way of strengthening the connectivity property of a graph [3]}, [2]}, [5]}. Hence tighter upper bounds on the rainbow connection number for graphs with higher connectivity have been a subject of investigation. The following are the results in this direction reported in literature: Let \(G\)  be a graph of order \(n\) . If \(G\)  is 2-edge-connected (bridgeless), then \(rc(G) \le 4n/5 -1\)  and if \(G\)  is 2-vertex-connected, then \(rc(G) \le \min \lbrace 2n/3, n/2 + O(\sqrt{n})\rbrace \)  [3]}. This was very recently improved in [7]}, where it was shown that if \(G\)  is 2-vertex-connected, then \(rc(G) \le \lceil n/2 \rceil \) , which is the best possible upper bound for the case. It also improved the previous best known upper bound of \(3(n+1)/5\)  for 3-vertex connected graphs [8]}. It was shown in [5]} that \(rc(G) \le 20n/\delta \)  where \(\delta \)  is the minimum degree of \(G\) . The result was improved in [10]} where it was shown that \(rc(G) \le 3n/(\delta + 1) + 3\) . Hence it follows that \(rc(G) \le 3n/(\lambda + 1) + 3\)  if \(G\)  is \(\lambda \) -edge-connected and \(rc(G) \le 3n/(\kappa + 1) + 3\)  if \(G\)  is \(\kappa \) -vertex-connected. It was shown in [7]} that the above bound in terms of edge connectivity is tight up to additive constants and that the bound in terms of vertex connectivity can be improved to \((2 + \epsilon )n/\kappa + 23/ \epsilon ^2\) , for any \(\epsilon > 0\) .
