Physical Sciences and Mathematics Commons^™

Note On Rainbow Connection In Oriented Graphs With Diameter 2, Rebecca Holliday, Colton Magnant, Pouria Salehi Nowbandegani

Theory and Applications of Graphs

In this note, we provide a sharp upper bound on the rainbow connection number of tournaments of diameter 2. For a tournament Τ of diameter 2, we show 2 ≤ → rc (Τ) ≤ 3. Furthermore, we provide a general upper bound on the rainbow κ-connection number of tournaments as a simple example of the probabilistic method. Finally, we show that an edge-colored tournament of κ^thdiameter 2 has rainbow κ-connection number at most approximately κ².