Rainbow connection of graphs with diameter 2

A path in an edge-colored graph G , where adjacent edges may have the same color, is a rainbow path if no two edges of the path are colored the same. The rainbow connection number r c ( G ) of G is the minimum integer k for which there exists a k -edge-coloring of G such that any two distinct vertices of G are connected by a rainbow path. It is known that for a graph G with diameter 2, deciding if r c ( G ) = 2 is NP-Complete. In particular, computing r c ( G ) is NP-hard. So, it is interesting to know the upper bound of r c ( G ) for such a graph G . In this paper, we show that r c ( G ) ≤ 5 if G is a bridgeless graph with diameter 2, and that r c ( G ) ≤ k + 2 if G is a connected graph with diameter 2 and has k bridges, where k ≥ 1 .