On strong rainbow connection number
On strong rainbow connection number
复制标题
DOI：
--
复制
发表时间：
2010-10
期刊：
影响因子：
--
通讯作者：
Xueliang Li;Yuefang Sun
中科院分区：
文献类型：
--
作者：
Xueliang Li;Yuefang Sun
在边着色图中，如果没有两条边着色相同，则相邻边着色相同的路径是彩虹路径。对于G的任意两个顶点u和v，G中的彩虹u-v测地线是长度为d（u，v）的彩虹u-v路，其中d（u，v）是u和v之间的距离。G的强彩虹连接数，记为src（G），是使G强彩虹连接所需的最小颜色数。本文首先研究了具有大强彩虹连通数的图。Chartrand等人得到了G是树当且仅当src（G）= m，我们将证明src（G）6 m−1，所以G不是树当且仅当src（G）m − 2，其中m是G的边数。此外，我们还刻画了src（G）= m − 2的图G。然后根据图G中边不相交三角形的个数给出了src（G）的一个精确上界，并给出了相等的一个充要条件.
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 src(G), is the minimum number of colors that are needed in order to make G strong rainbow connected. In this paper, we first investigate the graphs with large strong rainbow connection numbers. Chartrand et al. obtained that G is a tree if and only if src(G) = m, we will show that src(G) 6 m−1, so G is not a tree if and only if src(G) � m − 2, where m is the number of edge of G. Furthermore, we characterize the graphs G with src(G) = m − 2. We next give a sharp upper bound for src(G) according to the number of edge-disjoint triangles in graph G, and give a necessary and sufficient condition for the equality.