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 \( rc_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 \( rc_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 \( rc_k(G) \leq r \). Let \( s_k(n,r) \) denote the maximum number of edges in a \( k \)-connected graph \( G \) on \( n \) vertices with \( rc_k(G) \geq 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 \geq 3 \). We also provide some remarks about the function \( s_2(n,r) \).