Rainbow Connection in 3-Connected Graphs
Rainbow Connection in 3-Connected Graphs
复制标题
DOI：
10.1007/s00373-012-1204-9
复制
发表时间：
2012-07
影响因子：
0.7
通讯作者：
Xueliang Li;Yongtang Shi
中科院分区：
文献类型：
--
作者：
Xueliang Li;Yongtang Shi
一个边着色图G是彩虹连通的，如果任意两个顶点由一条边具有不同颜色的路连接。连通图G的彩虹连通数，记为rc（G），是使Grainbow连通所需的最小颜色数。本文证明了对所有3连通图，rc（G）≤ 3（n+ 1）/5.
An edge-colored graphGis rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graphG, denoted byrc(G), is the smallest number of colors that are needed in order to makeGrainbow connected. In this paper, we proved thatrc(G) ≤ 3(n+ 1)/5 for all 3-connected graphs.