Volume 36 • Number 2 • 2013   • On the Strong Rainbow Connection of a Graph Xueliang Li and Yuefang Sun Abstract. A path in an edge-colored graph, where adjacent edges may be colored the same, is a rainbow path if no two edges of it are colored the same. For any two vertices $u$ and $v$ of $G$, a rainbow $u-v$ geodesic in $G$ is a rainbow $u-v$ path of length $d(u,v)$, where $d(u,v)$ is the distance between $u$ and $v$. The graph $G$ is strongly rainbow connected if there exists a rainbow $u-v$ geodesic for any two vertices $u$ and $v$ in $G$. The strong rainbow connection number of $G$, denoted by $src(G)$, is the minimum number of colors that are needed in order to make $G$ strongly rainbow connected. In this paper, we first give a sharp upper bound for $src(G)$ in terms of the number of edge-disjoint triangles in a graph $G$, and give a necessary and sufficient condition for the equality. We next investigate the graphs with large strong rainbow connection numbers. Chartrand {\it et al.} obtained that $src(G)=m$ if and only if $G$ is a tree, we will show that $src(G)\neq m-1$, and characterize the graphs $G$ with $src(G)=m-2$ where $m$ is the number of edges of $G$. 2010 Mathematics Subject Classification: 05C15, 05C40 Full text: PDF