Rainbow Connection in Graphs with Minimum Degree Three
Rainbow Connection in Graphs with Minimum Degree Three
复制标题
DOI：
10.1007/978-3-642-10217-2_42
复制
发表时间：
2009-11
期刊：
影响因子：
--
通讯作者：
I. Schiermeyer
中科院分区：
文献类型：
--
作者：
I. Schiermeyer
边着色图G是彩虹连通图，如果任意两个顶点通过一条边具有不同颜色的路相连。连通图G的彩虹连通数，记为drc（G），是使彩虹连通所需的最小颜色数。本文证明了Caro等人[Y. Caro，A. Lev，Y. Roditty，Z. Tuza，和R. Yuster，On rainbow connection，The Electronic Journal of Combinatorics 15（2008），#57。
An edge-coloured graphGisrainbow connectedif any two vertices are connected by a path whose edges have distinct colours. Therainbow connection numberof a connected graphG, denotedrc(G), is the smallest number of colours that are needed in order to makeGrainbow connected. In this paper we prove thatfor graphs with minimum degree three, which was conjectured by Caro et al. [Y. Caro, A. Lev, Y. Roditty, Z. Tuza, and R. Yuster,On rainbow connection, The Electronic Journal of Combinatorics 15 (2008), #57.]