On the Strong Rainbow Connection of a Graph

Xueliang Li ; Yuefang Sun

Bulletin of the Malaysian Mathematical Society, Tome 36 (2013) no. 2

Résumé

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

Détail

Classification : 05C15, 05C40