Rainbow connection in oriented graphs
Rainbow connection in oriented graphs
复制标题
DOI：
10.1016/j.dam.2014.07.018
复制
发表时间：
2014-12
期刊：
影响因子：
--
通讯作者：
Paul Dorbec;I. Schiermeyer;E. Sidorowicz;É. Sopena
中科院分区：
文献类型：
--
作者：
Paul Dorbec;I. Schiermeyer;E. Sidorowicz;É. Sopena
一个边色图G称为彩虹连通图，如果任意两个顶点通过一条边具有不同颜色的路相连。图的彩虹连通数是使图彩虹连通所需的最小颜色数。这个图参数是由G. Chartrand，GL Johns，KA McKeon和P. Zhang，2008年。自那以后，这个话题引起了广泛的关注，并且引入了各种类似的参数，所有这些参数都用于处理无向图。在这里，我们开始研究有向图中的彩虹连通。一个早期的说法是，有向图的彩虹连接数的下界由它的直径决定，而上界由它的阶决定。我们首先刻画了彩虹连接数等于其阶的定向图。然后我们考虑竞赛图并证明了（i）竞赛图的彩虹连接数可以取2到其阶数减1的任何值，以及（ii）直径为d的每个竞赛图的彩虹连接数至多为d+ 2。
An edge-coloured graph G is said to be rainbow-connected if any two vertices are connected by a path whose edges have different colours. The rainbow connection number of a graph is the minimum number of colours needed to make the graph rainbow-connected. This graph parameter was introduced by G. Chartrand, GL Johns, KA McKeon and P. Zhang in 2008. Since, the topic drew much attention, and various similar parameters were introduced, all dealing with undirected graphs. Here, we initiate the study of rainbow connection in oriented graphs. An early statement is that the rainbow connection number of an oriented graph is lower bounded by its diameter and upper bounded by its order. We first characterize oriented graphs having rainbow connection number equal to their order. We then consider tournaments and prove that (i) the rainbow connection number of a tournament can take any value from 2 to its order minus one, and (ii) the rainbow connection number of every tournament with diameter d is at most d+ 2.