Mathematics – Combinatorics
Scientific paper
2011-11-15
Mathematics
Combinatorics
16 pages
Scientific paper
The oriented diameter of a bridgeless graph $G$ is $\min\{diam(H)\ | H\ is\ an orientation\ of\ G\}$. 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$.
Huang Xiaolong
Li Hengzhe
Li Xueliang
Sun Yuefang
No associations
LandOfFree
Oriented diameter and rainbow connection number of a graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Oriented diameter and rainbow connection number of a graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Oriented diameter and rainbow connection number of a graph will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-708799