广西师范学院学报（自然科学版）
廣西師範學院學報（自然科學版）
엄서사범학원학보（자연과학판）
Journal of Guangxi Teachers Education University (Natural Science Edition)
2015年
2期
1-5
,共5页
彩虹测地线%强彩虹连通数%边不交的圈
綵虹測地線%彊綵虹連通數%邊不交的圈
채홍측지선%강채홍련통수%변불교적권
rainbow geodesic%strong rainbow connection number%edge-disjoint cycle
如果图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‐圈图的一个强彩虹连通数的上界。接着给出了这个上界取等的充分条件。
如果圖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‐圈圖的一箇彊綵虹連通數的上界。接著給齣瞭這箇上界取等的充分條件。
여과도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 .
