Sufficient conditions for 2-rainbow connected graphs.

An edge-coloured connected graph G is rainbow connected if each two vertices are connected by a path whose edges have distinct colours. If such a colouring uses k colours then G is called k -rainbow connected. The rainbow connection number of G , denoted by rc ( G ) , is the minimum k such that G is k -rainbow connected. Even the problem to decide whether rc ( G ) = 2 is NP-complete. It has been shown that if G is a connected graph of order n and size m with n − 2 2 + 2 ≤ m ≤ n − 1 2 , then 2 ≤ rc ( G ) ≤ 3 . In this paper we will present sufficient conditions for graphs G of this size to fulfil rc ( G ) = 2 depending on vertex degrees. [ABSTRACT FROM AUTHOR]