Sufficient conditions for 2-rainbow connected graphs
An edge-coloured connected graph G G is rainbow connected if each two vertices are connected by a path whose edges have distinct colours. If such a colouring uses k k colours then G G is called k k -rainbow connected. The rainbow connection number of G G , denoted by rc ( G ) , is the minimum k k such that G G is k k -rainbow connected. Even the problem to decide whether rc ( G ) = 2 is NP-complete. It has been shown that if G G is a connected graph of order n n and size m 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 G of this size to fulfil rc ( G ) = 2 depending on vertex degrees.
rainbow connected rainbow colouring