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.
@article{bwmeta1.element.doi-10_7151_dmgt_1953,
author = {Jes\'us Alva-Samos and Juan Jos\'e Montellano-Ballesteros},
title = {Rainbow Connectivity of Cacti and of Some Infinite Digraphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {37},
year = {2017},
pages = {301-313},
zbl = {06705130},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1953}
}
Jesús Alva-Samos; Juan José Montellano-Ballesteros. Rainbow Connectivity of Cacti and of Some Infinite Digraphs. Discussiones Mathematicae Graph Theory, Tome 37 (2017) pp. 301-313. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1953/