Rainbow Connectivity of Cacti and of Some Infinite Digraphs

Jesús Alva-Samos, and Juan José Montellano-Ballesteros. "Rainbow Connectivity of Cacti and of Some Infinite Digraphs." Discussiones Mathematicae Graph Theory 37.2 (2017): 301-313. <http://eudml.org/doc/288026>.

@article{JesúsAlva2017,
abstract = {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.},
author = {Jesús Alva-Samos, Juan José Montellano-Ballesteros},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {rainbow connectivity; cactus; arc colouring},
language = {eng},
number = {2},
pages = {301-313},
title = {Rainbow Connectivity of Cacti and of Some Infinite Digraphs},
url = {http://eudml.org/doc/288026},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Jesús Alva-Samos
AU - Juan José Montellano-Ballesteros
TI - Rainbow Connectivity of Cacti and of Some Infinite Digraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 2
SP - 301
EP - 313
AB - 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.
LA - eng
KW - rainbow connectivity; cactus; arc colouring
UR - http://eudml.org/doc/288026
ER -