Quantcast

Rainbow Connection in Some Digraphs

Research paper by Jesús Alva-Samos, Juan José Montellano-Ballesteros

Indexed on: 11 Nov '16Published on: 01 Nov '16Published in: Graphs and Combinatorics



Abstract

Abstract An edge-coloured graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colours. This concept was introduced by Chartrand et al. (Math Bohemica 133(1):85–98, 2008), and it was extended to oriented graphs by Dorbec et al. (Discrete Appl Math 179(31):69–78, 2014). In this paper we present some results regarding this extension, mostly for the case of circulant digraphs.AbstractAn edge-coloured graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colours. This concept was introduced by Chartrand et al. (Math Bohemica 133(1):85–98, 2008), and it was extended to oriented graphs by Dorbec et al. (Discrete Appl Math 179(31):69–78, 2014). In this paper we present some results regarding this extension, mostly for the case of circulant digraphs.Grainbow connected20082014