On minimally rainbow k k -connected graphs
An edge-coloured graph G G is rainbow connected  if any two vertices are connected by a path whose edges have distinct colours. A graph G G is called rainbow k k -connected  if there is an edge colouring of G G with k k colours such that G G is rainbow connected. In this paper we will study rainbow k k -connected graphs with a minimum number of edges. For an integer n?3 n ? 3 and 1?k?n?1 1 ? k ? n ? 1 let t(n,k) t ( n , k ) denote the minimum size of a rainbow k k -connected graph G G of order n n . We will compute exact values and upper bounds for t(n,k) t ( n , k ) .
rainbow connection edge colouring minimally rainbow k k -connected k k k k k