Generalized Rainbow Connection of Graphs and their Complements

Abstract

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 Ḡ. 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(Ḡ) ≤ n + 2 for connected graphs G and Ḡ. The equality holds if and only if G or Ḡ is isomorphic to a double star.

Keywords

• ℓ-rainbow path
• (k, ℓ)-rainbow connected
• (k, ℓ)-rainbow connection number
• 04c15
• 05c40