Bulletin

Processing math: 100%

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