Upper bounds for the rainbow connection numbers of line graphs

Details Upper bounds for the rainbow connection numbers of line graphs Upper bounds for the rainbow connection numbers of line graphs

2010-01-02

arxiv.org/abs/1001.0287v1

Mathematics

Combinatorics

11 pages

Scientific paper

A path in an edge-colored graph $G$, where adjacent edges may be colored the same, is called a rainbow path if no two edges of it are colored the same. A nontrivial connected graph $G$ is rainbow connected if for any two vertices of $G$ there is a rainbow path connecting them. The rainbow connection number of $G$, denoted by $rc(G)$, is defined as the smallest number of colors by using which there is a coloring such that $G$ is rainbow connected. In this paper, we mainly study the rainbow connection number of the line graph of a graph which contains triangles and get two sharp upper bounds for $rc(L(G))$, in terms of the number of edge-disjoint triangles of $G$ where $L(G)$ is the line graph of $G$. We also give results on the iterated line graphs.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-233922