X. Li, C. Magnant, M. Wei, X. Zhu
Generalized rainbow connection of graphs and their complements
Discussiones Mathematicae Graph Theory
Received 26.07.2016, Revised 26.11.2016, Accepted 29.11.2016, doi: 10.7151/dmgt.2011

Let G be an edge-colored connected graph. A path P in G is called {ℓ}-rainbow if each subpath of length at most {ℓ}+1 is rainbow. The graph G is called (k,{ℓ})-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 {ℓ}-rainbow paths in G. The minimum number of colors needed to make G (k,{ℓ})-rainbow connected is called the (k,{ℓ})-rainbow connection number of G and denoted by rck,{ℓ}(G). In this paper, we first focus on the (1,2)-rainbow connection number of G depending on some constraints of ‾ 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 rc1,2(G)+rc1,2(‾{G})≤ n+2 for connected graphs G and ‾{G}. The equality holds if and only if G or ‾{G} is isomorphic to a double star.
{ℓ}-rainbow path, (k,{ℓ})-rainbow connected, (k,{ℓ})-rainbow connection number