2011/06/07 by Dong, Jiuying, Li, Xueliang
#05C15 #05C40 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1106.1258
Let G be a connected graph. The rainbow connection number rc(G) of a graph G was recently introduced by Chartrand et al. Li et al. proved that for every bridgeless graph G with diameter 2, rc(G)≤ 5. They gave examples for which rc(G)≤ 4. However, they could not show that the upper bound 5 is sharp. It is known that for a graph G with diameter 2, to determine rc(G) is NP-hard. So, it is interesting to know the best upper bound of rc(G) for such a graph G. In this paper, we use different way to obtain the same upper bound, and moreover, examples are given to show that the upper is best possible.