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/

[1] E. Andrews, E. Laforge, C. Lumduanhom and P. Zhang, On proper-path colorings in graphs, J. Combin. Math. Combin. Comput. 97 (2016) 189–207.

[2] V. Borozan, S. Fujita, A. Gerek, C. Magnant, Y. Manoussakis, L. Montero and Zs. Tuza, Proper connection of graphs, Discrete Math. 312 (2012) 2550–2560. doi:10.1016/j.disc.2011.09.003

[3] J.A. Bondy and U.S.R. Murty, Graph Therory (GTM 244, Springer-Verlag, New York, 2008).

[4] G. Chartrand, S. Devereaux and P. Zhang, Color-connected graphs and information-transfer paths, Ars Combin., to appear.

[5] G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang, Rainbow connection in graphs, Math. Bohem. 133 (2008) 85–98.

[6] S. Devereaux, G.L. Johns and P. Zhang, Color connection in graphs intermediate to proper and rainbow connection, J. Combin. Math. Combin. Comput., to appear.

[7] S. Devereaux and P. Zhang, k-rainbow colorings in graphs, manuscript.

[8] J.L. Fouquet and J.L. Jolivet, Strong edge-coloring of graphs and applications to multi-k-gons, Ars Combin. 16A (1983) 141–150.

[9] M. Krivelevich and R. Yuster, The rainbow connection of a graph is ( at most ) reciprocal to its minimum degree, J. Graph Theory 63 (2010) 185–191. doi:10.1002/jgt.20418

[10] X. Li and C. Magnant, Properly colored notions of connectivity—a dynamic survey, Theory Appl. Graphs 0(1) (2015) Article 2. doi:10.20429/tag.2015.000102

[11] X. Li, C. Magnant, M. Wei and X. Zhu, Distance proper connection of graphs (2016) arXiv:1606.06547 [math.CO]

[12] X. Li and Y. Shi, Rainbow connection in 3- connected graphs, Graphs Combin. 29 (2013) 1471–1475. doi:10.1007/s00373-012-1204-9

[13] X. Li, Y. Shi and Y. Sun, Rainbow connections of graphs: A survey, Graphs Combin. 29 (2013) 1–38. doi:10.1007/s00373-012-1243-2

[14] X. Li and Y. Sun, Rainbow Connections of Graphs (Springer Briefs in Math., Springer, New York, 2012).