Note on rainbow connection in oriented graphs with diameter 2
Note on rainbow connection in oriented graphs with diameter 2
复制标题
DOI：
10.20429/tag.2014.010102
复制
发表时间：
2014-11
期刊：
影响因子：
--
通讯作者：
Rebecca Holliday;Colton Magnant;P. S. Nowbandegani
中科院分区：
文献类型：
--
作者：
Rebecca Holliday;Colton Magnant;P. S. Nowbandegani
本文给出了直径为2的竞赛图的彩虹连接数的一个精确上界。对于直径为2的竞赛图T，我们证明2 ≤ − →rc（T）≤ 3。此外，我们提供了一个一般的上界彩虹k-连接数的比赛作为一个简单的例子的概率方法。最后，我们证明了第k个直径为2的边色竞赛图的彩虹k-连接数至多约为k2。
In this note, we provide a sharp upper bound on the rainbow connection number of tournaments of diameter 2. For a tournament T of diameter 2, we show 2 ≤ − →rc(T ) ≤ 3. Furthermore, we provide a general upper bound on the rainbow k-connection number of tournaments as a simple example of the probabilistic method. Finally, we show that an edge-colored tournament of kth diameter 2 has rainbow k-connection number at most approximately k2.