On Rainbow Connection
On Rainbow Connection
复制标题
DOI：
10.37236/781
复制
发表时间：
2008-04
期刊：
影响因子：
--
通讯作者：
Y. Caro;A. Lev;Y. Roditty;Z. Tuza;R. Yuster
中科院分区：
文献类型：
--
作者：
Y. Caro;A. Lev;Y. Roditty;Z. Tuza;R. Yuster
如果任意两个顶点通过一条边具有不同颜色的路径连接，则边彩色图 $G$ 是彩虹连通的。连接图 $G$ 的彩虹连接数，表示为 $rc(G)$，是使 $G$ 彩虹连接所需的最小颜色数。在本文中，我们证明了 $rc(G)$ 的几个重要上限，并确定了保证 $rc(G)=2$ 的充分条件。在我们的结果中，我们证明，如果 $G$ 是具有 $n$ 个顶点且最小度为 $3$ 的连通图，则 $rc(G)
An edge-colored graph $G$ is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph $G$, denoted $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. In this paper we prove several non-trivial upper bounds for $rc(G)$, as well as determine sufficient conditions that guarantee $rc(G)=2$. Among our results we prove that if $G$ is a connected graph with $n$ vertices and with minimum degree $3$ then $rc(G)