Rainbow Connectivity of Cacti and of Some Infinite Digraphs

• Autorzy: Jesús Alva-Samos , Juan José Montellano-Ballesteros
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

rainbow connectivity; cactus; arc colouring

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 2
• Strony: 301-313

Daty

wydano

2017-05-01

otrzymano

2015-11-29

poprawiono

2016-08-03

zaakceptowano

2016-10-21

online

2017-04-01

Twórcy

autor

Jesús Alva-Samos

• Instituto de Matemáticas, Universidad Nacional Autónoma de México Área de la Investigación Científica, Ciudad Universitaria Coyoacán 04510 México, CDMX,,

autor

Juan José Montellano-Ballesteros

• Instituto de Matemáticas, Universidad Nacional Autónoma de México Área de la Investigación Científica, Ciudad Universitaria Coyoacán 04510 México, CDMX,,

Identyfikatory

DOI

10.7151/dmgt.1953