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/