Let fc be a positive integer, and G be a fc-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 rck(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 rck(G) was introduced by Chartrand, Johns, McKeon and Zhang in 2009, and has since attracted significant interest. Let tk(n,r) denote the minimum number of edges in a k-connected graph G on n vertices with rck(G) ≤ r. Let Sk(n,r) denote the maximum number of edges in a k-connected graph G on n vertices with rck(G) ≥ r. The functions t1(n,r) and s1(n,r) have previously been studied by various authors. In this paper, we study the functions t2(n,r) and s2(n,r). We determine bounds for t2(n,r) which imply that t2(n, 2) = (1 + o(l))nlog2n, and t2(n, r) is linear in n for r ≥ 3. We also provide some remarks about the function s2(n,r).
Shinya Fujita is supported by JSPS KAKENHI (No. 19K03603). Henry Liu is partially supported by the Startup Fund of One Hundred Talent Program of SYSU, and National Natural Science Foundation of China (No. 11931002). Boram Park is supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT and Future Planning (NRF-2018R1C1B6003577). Shinya Fujita and Boram Park acknowledge the generous hospitality of Sun Yat-sen University, Guangzhou, China. They were able to carry out part of this research with Henry Liu during their visits there in 2019. The authors would like to thank the anonymous referee for valuable comments and suggestions.
