Author/Authors :
Perla Ekstein، نويسنده , , Jan and Holub، نويسنده , , P?emysl and Kaiser، نويسنده , , Tomas and Koch، نويسنده , , Maria Izabel Camacho، نويسنده , , Stephan Matos and Ryj??ek، نويسنده , , Zden?k and Schiermeyer، نويسنده , , Ingo، نويسنده ,
Abstract :
The rainbow connection number of a graph G is the least number of colours in a (not necessarily proper) edge-colouring of G such that every two vertices are joined by a path which contains no colour twice. Improving a result of Caro et al., we prove that the rainbow connection number of every 2-connected graph with n vertices is at most ⌈ n / 2 ⌉ . The bound is optimal.
Keywords :
05C15 , Rainbow connection number , connectivity , graph
