Geodesic
On rainbow connection
The electronic journal of combinatorics, Tome 15 (2008)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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) < 5n/6$, and if the minimum degree is $\delta$ then $rc(G) \le {\ln \delta\over\delta}n(1+o_\delta(1))$. We also determine the threshold function for a random graph to have $rc(G)=2$ and make several conjectures concerning the computational complexity of rainbow connection.
DOI : 10.37236/781
Classification : 05C15, 05C40 
@article{10_37236_781,
     author = {Yair Caro and Arie Lev and Yehuda Roditty and Zsolt Tuza and Raphael Yuster},
     title = {On rainbow connection},
     journal = {The electronic journal of combinatorics},
     year = {2008},
     volume = {15},
     doi = {10.37236/781},
     zbl = {1181.05037},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/781/}
}
TY  - JOUR
AU  - Yair Caro
AU  - Arie Lev
AU  - Yehuda Roditty
AU  - Zsolt Tuza
AU  - Raphael Yuster
TI  - On rainbow connection
JO  - The electronic journal of combinatorics
PY  - 2008
VL  - 15
UR  - http://geodesic.mathdoc.fr/articles/10.37236/781/
DO  - 10.37236/781
ID  - 10_37236_781
ER  - 
%0 Journal Article
%A Yair Caro
%A Arie Lev
%A Yehuda Roditty
%A Zsolt Tuza
%A Raphael Yuster
%T On rainbow connection
%J The electronic journal of combinatorics
%D 2008
%V 15
%U http://geodesic.mathdoc.fr/articles/10.37236/781/
%R 10.37236/781
%F 10_37236_781
Yair Caro; Arie Lev; Yehuda Roditty; Zsolt Tuza; Raphael Yuster. On rainbow connection. The electronic journal of combinatorics, Tome 15 (2008). doi: 10.37236/781

Cité par Sources :