Abstract
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.