Generalized Rainbow Connection of Graphs and their Complements

Let $G$ be an edge-colored connected graph. A path $P$ in $G$ is called $ \mathcal{l} $-rainbow if each subpath of length at most $ \mathcal{l} + 1 $ is rainbow. The graph $G$ is called $(k, \mathcal{l} )$-rainbow connected if there is an edge-coloring such that every pair of distinct vertices of $G$ is connected by $k$ pairwise internally vertex-disjoint $ \mathcal{l} $-rainbow paths in $G$. The minimum number of colors needed to make $G$ $(k, \mathcal{l})$-rainbow connected is called the $ (k, \mathcal{l} )$-rainbow connection number of $G$ and denoted by $ rc_{ k,\mathcal{l} } (G) $. In this paper, we first focus on the (1, 2)-rainbow connection number of $G$ depending on some constraints of $ \overline{G} $. Then, we characterize the graphs of order $n$ with (1, 2)-rainbow connection number $ n − 1 $ or $ n − 2 $. Using this result, we investigate the Nordhaus-Gaddum-Type problem of (1, 2)-rainbow connection number and prove that $ rc_{1,2}(G) + rc_{1,2}( \overlina{G} ) \le n + 2 $ for connected graphs $ G $ and $ \overline{G} $. The equality holds if and only if $G$ or $ \overline{G} $ is isomorphic to a double star.