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 l-rainbow if each subpath of length at most l+1 is rainbow. The graph G is called (k,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 l-rainbow paths in G. The minimum number of colors needed 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 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.
l-rainbow path, (k,l)-rainbow connected, (k,l)-rainbow connection number