On minimally rainbow kk-connected graphs

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

► In this paper, edge colourings of graphs are considered.
► A path between two vertices whose edges are coloured distinctly is a rainbow path.
► GG is called rainbow connected if all pairs of vertices have a rainbow path.
► GG is called rainbow kk-connected if the edges of GG are coloured with kk colours.
► We are studying rainbow kk-connected graphs with a minimum number of edges.