Sharp upper bound for the rainbow connection number of a graph with diameter 2

Abstract

Let $G$ be a connected graph. The \emph{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)\le 5$. They gave examples for which $rc(G)\le 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.

7 pages

References in corpus (2)

• Rainbow Connection Number and Radius
• Rainbow connection of graphs with diameter 2

Cited by in corpus (3)

• Rainbow connections for planar graphs and line graphs
• Rainbow connection of bridgeless outerplanar graphs with small diameters
• On a question on graphs with rainbow connection number 2