Search

The rainbow connection number of a connected graph is the minimum number of colors needed to color its edges, so that every pair of its vertices is connected by at least one path in which no two edges are colored the same. In this article we show that for every connected graph on n vertices with minimum degree δ, the rainbow connection number is upper bounded by 3 n/(δ + 1) + 3. This solves an open problem from Schiermeyer (Combinatorial Algorithms, Springer, Berlin/Hiedelberg, 2009, pp. 432-437), improving the previously best known bound of 20 n/δ (J Graph Theory 63 (2010), 185-191). This bound is tight up to additive factors by a construction mentioned in Caro et al. (Electr J Combin 15(R57) (2008), 1). As an intermediate step we obtain an upper bound of 3 n/(δ + 1) − 2 on the size of a connected two-step dominating set in a connected graph of order n and minimum degree δ. This bound is tight up to an additive constant of 2. This result may be of independent interest. We also show that for every connected graph G with minimum degree at least 2, the rainbow connection number, rc( G), is upper bounded by Γ c( G) + 2, where Γ c( G) is the connected domination number of G. Bounds of the form diameter( G)⩽ rc( G)⩽ diameter( G) + c, 1⩽ c⩽4, for many special graph classes follow as easy corollaries from this result. This includes interval graphs, asteroidal triple-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)⩽3· radius( G). In most of these cases, we also demonstrate the tightness of the bounds. [ABSTRACT FROM AUTHOR]