- Tytuł:
- Rainbow Connectivity of Cacti and of Some Infinite Digraphs
- Autorzy:
-
Alva-Samos, Jesús
Montellano-Ballesteros, Juan José - Powiązania:
- https://bibliotekanauki.pl/articles/31341981.pdf
- Data publikacji:
- 2017-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
rainbow connectivity
cactus
arc colouring - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2017, 37, 2; 301-313
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł