2010/01/02 by Xueliang Li, Li, Xueliang, Yuefang Sun +1
Mathematics · #05C15 #05C40 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15 #msc:05C40
paper · pdf · doi:10.48550/arxiv.1001.0287
11 pages
arxiv created 2010/01/02 · arxiv updated 2010/01/14
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.