(1, 2)-rainbow connection number at most 3 in connected dense graphs - Trung Duy Doan; Le Thi Duyen (Electronic Journal of Graph Theory and Applications (EJGTA), 2023)
Let G be an edge-coloured connected graph G. A path P in the graph G is called l-rainbow path if each subpath of length at most l + 1 is rainbow. The graph G is called (k, l)-rainbow connected if any two vertices in G are connected by at least k pairwise internally vertex-disjoint l-rainbow paths. The smallest number of colours needed in order to make G (k, l)-rainbow connected is called the (k, l)-rainbow connection number of G and denoted by rck, l(G). In this paper, we consider the (1, 2)-rainbow connection number at most 3 in some connected dense graphs. Our main results are as follows: (1) Let n ≥ 7 be an integer and G be a connected graph of order n. If ω(G)≥n − 3, then rc1, 2(G)≤3. Moreover, the bound of the clique number is sharpness. (2) Let n ≥ 7 be an integer and G be a connected graph of order n. If |E(G)| ≥ C(n − 3, 2)+7, then rc1, 2(G)≤3.