Rainbow connection of graphs with diameter 2

Details Rainbow connection of graphs with diameter 2 Rainbow connection of graphs with diameter 2

2011-01-14

arxiv.org/abs/1101.2765v2

Mathematics

Combinatorics

10 pages

Scientific paper

A path in an edge-colored graph $G$, where adjacent edges may have the same color, is called a rainbow path if no two edges of the path are colored the same. The rainbow connection number $rc(G)$ of $G$ is the minimum integer $i$ for which there exists an $i$-edge-coloring of $G$ such that every two distinct vertices of $G$ are connected by a rainbow path. It is known that for a graph $G$ with diameter 2, to determine $rc(G)$ is NP-hard. So, it is interesting to know the best upper bound of $rc(G)$ for such a graph $G$. In this paper, we show that $rc(G)\leq 5$ if $G$ is a bridgeless graph with diameter 2, and that $rc(G)\leq k+2$ if $G$ is a connected graph of diameter 2 with $k$ bridges, where $k\geq 1$.

Affiliated with

Also associated with

No associations

Rating

Rainbow connection of graphs with diameter 2 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 Rainbow connection of graphs with diameter 2, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rainbow connection of graphs with diameter 2 will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-79018