pith. sign in

arxiv: 1001.0287 · v1 · submitted 2010-01-02 · 🧮 math.CO

Upper bounds for the rainbow connection numbers of line graphs

classification 🧮 math.CO
keywords rainbowgraphlinenumberconnectedconnectionpathbounds
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.