Rainbow connection in graphs

Let $G$ be a nontrivial connected graph on which is defined a coloring $c: E(G) rightarrow lbrace 1, 2, ldots , krbrace $, $k in {mathbb{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 $mathop {mathrm 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 $mathop {mathrm src}(G)$ of $G$. Thus $mathop {mathrm rc}(G) le mathop {mathrm src}(G)$ for every nontrivial connected graph $G$. Both $mathop {mathrm rc}(G)$ and $mathop {mathrm 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 ge 3$ and $b ge (5a-6)/3$, it is shown that there exists a connected graph $G$ such that $mathop {mathrm rc}(G)=a$ and $mathop {mathrm src}(G)=b$.