pith. sign in

arxiv: 1106.1258 · v3 · pith:5BPQHXZNnew · submitted 2011-06-07 · 🧮 math.CO

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

classification 🧮 math.CO
keywords graphupperbounddiameterbestconnectionexamplesnumber
0
0 comments X
read the original 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)\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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.