Mathematics – Combinatorics
Scientific paper
2010-11-02
Mathematics
Combinatorics
6 pages, 2 figures
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 note we show that for every bridgeless graph G with radius r, rc(G) <= r(r+2). We demonstrate that this bound is the best possible for rc(G) as a function of r, not just for bridgeless graphs, but also for graphs of any stronger connectivity. It may be noted that, for a general 1-connected graph G, rc(G) can be arbitrarily larger than its radius (K_{1,n} for instance). We further show that for every bridgeless graph G with radius r and chordality (size of a largest induced cycle) k, rc(G) <= rk. Hitherto, the only reported upper bound on the rainbow connection number of bridgeless graphs is 4n/5 - 1, where n is order of the graph [Caro et al., 2008]
Basavaraju Manu
Chandran Sunil L.
Rajendraprasad Deepak
Ramaswamy Arunselvan
No associations
LandOfFree
Rainbow Connection Number and Radius 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 Rainbow Connection Number and Radius, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rainbow Connection Number and Radius will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-595737