Mathematics – Combinatorics
Scientific paper
2010-10-12
Mathematics
Combinatorics
14 pages
Scientific paper
10.1002/jgt.20643
Rainbow connection number rc(G) of a connected graph G is the minimum number of colours needed to colour the edges of G, 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 show that for every connected graph G, with minimum degree at least 2, the rainbow connection number is upper bounded by {\gamma}_c(G) + 2, where {\gamma}_c(G) is the connected domination number of G. Bounds of the form diameter(G) \leq rc(G) \leq diameter(G) + c, 1 \leq c \leq 4, for many special graph classes follow as easy corollaries from this result. This includes interval graphs, AT-free graphs, circular arc graphs, threshold graphs, and chain graphs all with minimum degree at least 2 and connected. We also show that every bridge-less chordal graph G has rc(G) \leq 3.radius(G). In most of these cases, we also demonstrate the tightness of the bounds. An extension of this idea to two-step dominating sets is used to show that for every connected graph on n vertices with minimum degree {\delta}, the rainbow connection number is upper bounded by 3n/({\delta} + 1) + 3. This solves an open problem of Schiermeyer (2009), improving the previously best known bound of 20n/{\delta} by Krivelevich and Yuster (2010). Moreover, this bound is seen to be tight up to additive factors by a construction of Caro et al. (2008).
Chandran Sunil L.
Das Anita
Rajendraprasad Deepak
Varma Nithin M.
No associations
LandOfFree
Rainbow Connection Number and Connected Dominating Sets 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 Connected Dominating Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rainbow Connection Number and Connected Dominating Sets will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-607884