Rainbow connection in graphs

Let G be a nontrivial connected graph on which is defined a coloring c\: E(G) → 1, 2, … , k, k ∈ N, of the edges of G, where adjacent edges may be colored the same. A path P in G is a rainbow path if no two edges of P are colored the same. The graph G is rainbow-connected if G contains a rainbow $u-v$ path for every two vertices u and v of G. The minimum k for which there exists such a k-edge coloring is the rainbow connection number rc(G) of G. If for every pair $u, v$ of distinct vertices, G contains a rainbow $u-v$ geodesic, then G is strongly rainbow-connected. The minimum k for which there exists a k-edge coloring of G that results in a strongly rainbow-connected graph is called the strong rainbow connection number src(G) of G. Thus rc(G) ≤ src(G) for every nontrivial connected graph G. Both rc(G) and src(G) are determined for all complete multipartite graphs G as well as other classes of graphs. For every pair $a, b$ of integers with a ≥ 3 and b ≥ (5a-6)/3, it is shown that there exists a connected graph G such that rc(G)=a and src(G)=b.