Rainbow connectivity of cacti and some infinite digraphs
Jesús Alva‐Samos, Juan José Montellano‐Ballesteros · Discussiones Mathematicae Graph Theory · 2017
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 connection 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.