摘要
如果图G的任意两个顶点由一条路P连接，其中路P的每一条边着不同的颜色，则称图G为彩虹连通图。对图G的任意两个顶点u和v ，G的彩虹u － v测地线是一条长为d（u ，v ）的彩虹路，其中d（u ，v ）表示最短的u－ v路的长度。图 G称为强彩虹连通的如果对G的任意两点u和v间都存在一条彩虹u － v测地线。图G的强彩虹连通数是指使得图G是强彩虹连通而用的最少颜色的数目，用src（G ）表示。该文首先给出了一个含边不交的k‐圈图的一个强彩虹连通数的上界。接着给出了这个上界取等的充分条件。
Abstract
A graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors .For 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 length of a shortest u - v path in G .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 ,denoted by src(G ) ,of a connected graph G is the minimum number of colors needed to color its edges ,so that G is strongly rainbow connected .In this paper ,we first give an upper bound for the strong rainbow connection number of graphs depending on the num‐ber of edge‐disjoint k‐cycle .Moreover ,we give a sufficient condition for the equality .
NETL
NSTL
维普
万方数据