Oriented diameter and rainbow connection number of a graph

Abstract

The oriented diameter of a bridgeless graph $G$ is $\min \{diam(H)|HisanorientationofG\}$. A path in an edge-colored graph $G$, where adjacent edges may have the same color, is called rainbow if no two edges of the path are colored the same. The rainbow connection number $rc(G)$ of $G$ is the smallest integer $k$ for which there exists a $k$-edge-coloring of $G$ such that every two distinct vertices of $G$ are connected by a rainbow path. In this paper, we obtain upper bounds for the oriented diameter and the rainbow connection number of a graph in terms of $rad(G)$ and $\eta (G)$, where $rad(G)$ is the radius of $G$ and $\eta (G)$ is the smallest integer number such that every edge of $G$ is contained in a cycle of length at most $\eta (G)$. We also obtain constant bounds of the oriented diameter and the rainbow connection number for a (bipartite) graph $G$ in terms of the minimum degree of $G$.

16 pages

References in corpus (1)

• Rainbow Connection Number and Radius