The size of graphs with restricted rainbow 2-connection number - Fujita, Shinya; Liu, Henry; Park, Boram (Journal of Combinatorial Mathematics and Combinatorial Computing, 2021)
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).
Keywords: Connected graph; Connection number; Edge-colouring; K-connected graphs; Positive integers; Vertex disjoint; Edge-colouring; k-connected graph; Rainbow (k-) connection number