Geodesic
Generalized Rainbow Connection of Graphs and their Complements
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 371-384

Voir la notice de l'article provenant de la source Library of Science

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 rc_ k,𝓁 (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: ℓ-rainbow path, ( k, ℓ)-rainbow connected, ( k, ℓ)-rainbow connection number 
@article{DMGT_2018_38_2_a2,
     author = {Li, Xueliang and Magnant, Colton and Wei, Meiqin and Zhu, Xiaoyu},
     title = {Generalized {Rainbow} {Connection} of {Graphs} and their {Complements}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {371--384},
     publisher = {mathdoc},
     volume = {38},
     number = {2},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a2/}
}
TY  - JOUR
AU  - Li, Xueliang
AU  - Magnant, Colton
AU  - Wei, Meiqin
AU  - Zhu, Xiaoyu
TI  - Generalized Rainbow Connection of Graphs and their Complements
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 371
EP  - 384
VL  - 38
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a2/
LA  - en
ID  - DMGT_2018_38_2_a2
ER  - 
%0 Journal Article
%A Li, Xueliang
%A Magnant, Colton
%A Wei, Meiqin
%A Zhu, Xiaoyu
%T Generalized Rainbow Connection of Graphs and their Complements
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 371-384
%V 38
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a2/
%G en
%F DMGT_2018_38_2_a2
Li, Xueliang; Magnant, Colton; Wei, Meiqin; Zhu, Xiaoyu. Generalized Rainbow Connection of Graphs and their Complements. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 371-384. http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a2/