Geodesic
Rainbow Connectivity of Cacti and of Some Infinite Digraphs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 2, pp. 301-313.

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

An arc-coloured digraph D = (V,A) is said to be rainbow connected if for every pair u, v ⊆ V there is a directed uv-path all whose arcs have different colours and a directed vu-path all whose arcs have different colours. The minimum number of colours required to make the digraph D rainbow connected is called the rainbow connection number of D, denoted rc⃗ (D). A cactus is a digraph where each arc belongs to exactly one directed cycle. In this paper we give sharp upper and lower bounds for the rainbow connection number of a cactus and characterize those cacti whose rainbow connection number is equal to any of those bounds. Also, we calculate the rainbow con- nection numbers of some infinite digraphs and graphs, and present, for each n ≥ 6, a tournament of order n and rainbow connection number equal to 2.
Keywords: rainbow connectivity, cactus, arc colouring 
@article{DMGT_2017_37_2_a0,
     author = {Alva-Samos, Jes\'us and Montellano-Ballesteros, Juan Jos\'e},
     title = {Rainbow {Connectivity} of {Cacti} and of {Some} {Infinite} {Digraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {301--313},
     publisher = {mathdoc},
     volume = {37},
     number = {2},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a0/}
}
TY  - JOUR
AU  - Alva-Samos, Jesús
AU  - Montellano-Ballesteros, Juan José
TI  - Rainbow Connectivity of Cacti and of Some Infinite Digraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 301
EP  - 313
VL  - 37
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a0/
LA  - en
ID  - DMGT_2017_37_2_a0
ER  - 
%0 Journal Article
%A Alva-Samos, Jesús
%A Montellano-Ballesteros, Juan José
%T Rainbow Connectivity of Cacti and of Some Infinite Digraphs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 301-313
%V 37
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a0/
%G en
%F DMGT_2017_37_2_a0
Alva-Samos, Jesús; Montellano-Ballesteros, Juan José. Rainbow Connectivity of Cacti and of Some Infinite Digraphs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 2, pp. 301-313. http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a0/

[1] J. Alva-Samos and J.J. Montellano-Ballesteros, Rainbow connection in some digraphs, Graphs Combin. 32 (2016) 2199-2209. doi: 10.1007/s00373-016-1723-x

[2] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer-Verlag, 2002). doi: 10.1007/978-1-4471-3886-0

[3] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer-Verlag, 2008).

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

[5] P. Dorbec, I. Schiermeyer, E. Sidorowicz and E. Sopena, Rainbow connection in oriented graphs, Discrete Appl. Math. 179 (2014) 69-78. doi: 10.1016/j.dam.2014.07.018

[6] R. Holliday, C. Magnant and P.S. Nowbandegani, Note on rainbow connection in oriented graphs with diameter 2, Theory Appl. Graphs 1 (2014).