The rainbow connection of a graph is (at most) reciprocal to its minimum degree
The rainbow connection of a graph is (at most) reciprocal to its minimum degree
复制标题
DOI：
10.1002/jgt.20418
复制
发表时间：
2010-03
影响因子：
0.9
通讯作者：
Michael Krivelevich;R. Yuster
中科院分区：
文献类型：
--
作者：
Michael Krivelevich;R. Yuster
一个边着色图G是彩虹边连通的，如果任意两个顶点由一条边具有不同颜色的路连接。连通图G的彩虹连接，记为rc（G），是为了使Grainbow边连通所需的最小颜色数。证明了若G有n个顶点且最小度为δ，则rc（G）<20 n/δ.这解决了Y的开放问题。Caro，A. Lev，Y. Roditty，Z. Tuza，和R. Yuster（Electron J Combin 15（2008），#R57）和S. Chakrborty，E. Fischer，A.菲舍尔，A. Matsliah和R. Yuster（Hardness and algorithms for rainbow connectivity，弗赖堡（2009），pp. 243-254）。一个顶点着色图G是彩虹顶点连通的，如果任意两个顶点由一条内部顶点具有不同颜色的路连接。一个连通图G的彩虹顶点连通，记为rvc（G），是为了使Grainbow顶点连通所需的最小颜色数。人们不能根据另一个参数来确定其中一个参数的上限。然而，我们证明了：如果G有n个顶点且最小度δ，则rvc（G）<11n/δ.我们注意到，这种情况下的证明与边缘着色情况下的证明不同，我们不能从另一个推导出一个。© 2009威利期刊公司. J Graph Theory 63：185-191，2010
An edge‐colored graph Gis rainbow edge‐connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make Grainbow edge‐connected. We prove that if Ghas nvertices and minimum degree δ then rc(G)<20n/δ. This solves open problems from Y. Caro, A. Lev, Y. Roditty, Z. Tuza, and R. Yuster (Electron J Combin 15 (2008), #R57) and S. Chakrborty, E. Fischer, A. Matsliah, and R. Yuster (Hardness and algorithms for rainbow connectivity, Freiburg (2009), pp. 243–254). A vertex‐colored graph Gis rainbow vertex‐connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex‐connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make Grainbow vertex‐connected. One cannot upper‐bound one of these parameters in terms of the other. Nevertheless, we prove that if Ghas nvertices and minimum degree δ then rvc(G)<11n/δ. We note that the proof in this case is different from the proof for the edge‐colored case, and we cannot deduce one from the other. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 185–191, 2010