paper

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

arXiv:1106.1258

Abstract

Let be a connected graph. The \emph{rainbow connection number } of a graph was recently introduced by Chartrand et al. Li et al. proved that for every bridgeless graph with diameter 2, . They gave examples for which . However, they could not show that the upper bound 5 is sharp. It is known that for a graph with diameter 2, to determine is NP-hard. So, it is interesting to know the best upper bound of for such a graph . 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.

arXiv comment7 pages

References in corpus (2)

Cited by in corpus (3)