Mathematics – Combinatorics
Scientific paper
2011-05-28
Mathematics
Combinatorics
10 pages
Scientific paper
Rainbow connection number, $rc(G)$, of a connected graph $G$ is the minimum number of colours needed to colour its edges, so that every pair of vertices is connected by at least one path in which no two edges are coloured the same. In this paper we investigate the relationship of rainbow connection number with vertex and edge connectivity. It is already known that for a connected graph with minimum degree $\delta$, the rainbow connection number is upper bounded by $3n/(\delta + 1) + 3$ [Chandran et al., 2010]. This directly gives an upper bound of $3n/(\lambda + 1) + 3$ and $3n/(\kappa + 1) + 3$ for rainbow connection number where $\lambda$ and $\kappa$, respectively, denote the edge and vertex connectivity of the graph. We show that the above bound in terms of edge connectivity is tight up-to additive constants and show that the bound in terms of vertex connectivity can be improved to $(2 + \epsilon)n/\kappa + 23/ \epsilon^2$, for any $\epsilon > 0$. We conjecture that rainbow connection number is upper bounded by $n/\kappa + O(1)$ and show that it is true for $\kappa = 2$. We also show that the conjecture is true for chordal graphs and graphs of girth at least 7.
Chandran Sunil L.
Mathew Rogers
Rajendraprasad Deepak
No associations
LandOfFree
On Rainbow Connection Number and Connectivity 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 On Rainbow Connection Number and Connectivity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Rainbow Connection Number and Connectivity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-49752