Rainbow $k$-Connection in Dense Graphs

Abstract

An edge-coloured path is rainbow if the colours of its edges are distinct. For a positive integer $k$, an edge-colouring of a graph $G$ is rainbow $k$-connected if any two vertices of $G$ are connected by $k$ internally vertex-disjoint rainbow paths. The rainbow $k$-connection number $r{c}_k(G)$ is defined to be the minimum integer $t$ such that there exists an edge-colouring of $G$ with $t$ colours which is rainbow $k$-connected. We consider $r{c}_2(G)$ when $G$ has fixed vertex-connectivity. We also consider $r{c}_k(G)$ for large complete bipartite and multipartite graphs $G$ with equipartitions. Finally, we determine sharp threshold functions for the properties $r{c}_k(G)=2$ and $r{c}_k(G)=3$, where $G$ is a random graph. Related open problems are posed.