The size of graphs with restricted rainbow 2-connection number

Abstract

Let $k$ be a positive integer, and $G$ be a $k$-connected graph. An edge-coloured path is rainbow if all of its edges have distinct colours. The rainbow $k$-connection number of $G$, denoted by $r{c}_k(G)$, is the minimum number of colours in an edge-colouring of $G$ such that, any two vertices are connected by $k$ internally vertex-disjoint rainbow paths. The function $r{c}_k(G)$ was introduced by Chartrand, Johns, McKeon, and Zhang in 2009, and has since attracted significant interest. Let $t_k(n,r)$ denote the minimum number of edges in a $k$-connected graph $G$ on $n$ vertices with $r{c}_k(G)\le r$. Let $s_k(n,r)$ denote the maximum number of edges in a $k$-connected graph $G$ on $n$ vertices with $r{c}_k(G)\ge r$. The functions $t_1(n,r)$ and $s_1(n,r)$ have previously been studied by various authors. In this paper, we study the functions $t_2(n,r)$ and $s_2(n,r)$. We determine bounds for $t_2(n,r)$ which imply that $t_2(n,2)=(1+o(1))n{\log }_{2}n$, and $t_2(n,r)$ is linear in $n$ for $r\ge 3$. We also provide some remarks about the function $s_2(n,r)$.