图的强彩虹连通数

Strong Rainbow Connection Number of Graph

如果图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-圈图的一个强彩虹连通数的上界.接着给出了这个上界取等的充分条件.

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.