Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647815 | Discrete Mathematics | 2012 | 5 Pages |
A path in an edge-colored graph GG, 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 rc(G)rc(G) of GG is the minimum integer kk for which there exists a kk-edge-coloring of GG such that any two distinct vertices of GG are connected by a rainbow path. It is known that for a graph GG with diameter 2, deciding if rc(G)=2rc(G)=2 is NP-Complete. In particular, computing rc(G)rc(G) is NP-hard. So, it is interesting to know the upper bound of rc(G)rc(G) for such a graph GG. In this paper, we show that rc(G)≤5rc(G)≤5 if GG is a bridgeless graph with diameter 2, and that rc(G)≤k+2rc(G)≤k+2 if GG is a connected graph with diameter 2 and has kk bridges, where k≥1k≥1.