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

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

2011-06-07

arxiv.org/abs/1106.1258v3

Mathematics

Combinatorics

7 pages

Scientific paper

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)\leq 5$. They gave examples for which $rc(G)\leq 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.

Affiliated with

Also associated with

No associations

Rating

Sharp upper bound for the rainbow connection number of a graph with diameter 2 does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sharp upper bound for the rainbow connection number of a graph with diameter 2, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sharp upper bound for the rainbow connection number of a graph with diameter 2 will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-26221