Rainbow connection numbers of line graphs, middle graphs and total graphs
Yuefang Sun · International Journal of Applied Mathematics & Statistics/International journal of applied mathematics and statistics · 2013
A path in an edge-colored graph, where adjacent edges may be colored the same,is a rainbow path if no two edges of it are colored the same. A nontrivial connected graph G is rainbow connected if there is a rainbow path connecting any two vertices, and the rainbow connection number of G, denoted rc(G), is the minimum number of colors that are needed in order to make G rainbow connected. In this paper, we investigate the rainbow connection numbers of the line graph, middle graph and total graph of a connected triangle-free graph G. We obtain three (near) sharp upper bounds in terms of the number of vertex-disjoint cycles of the original graph G.