Authors: X. Li, C. Magnant, M. Wei, X. Zhu Title: Generalized rainbow connection of graphs and their complements Source: Discussiones Mathematicae Graph Theory Received 26.07.2016, Revised 26.11.2016, Accepted 29.11.2016, doi: 10.7151/dmgt.2011 | |
Abstract: 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 rc_{k,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 rc_{1,2}(G)+rc_{1,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. | |
Keywords: l-rainbow path, (k,l)-rainbow connected, (k,l)-rainbow connection number | |
Links: |