pith. sign in

arxiv: 1211.0141 · v2 · pith:V7FWOJSRnew · submitted 2012-11-01 · 🧮 math.CO

Rainbow connection number and the number of blocks

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

An edge-colored graph $G$ is rainbow connected if every pair of vertices of $G$ are connected by a path whose edges have distinct colors. The rainbow connection number $rc(G)$ of $G$ is defined to be the minimum integer $t$ such that there exists an edge-coloring of $G$ with $t$ colors that makes $G$ rainbow connected. For a graph $G$ without any cut vertex, i.e., a 2-connected graph, of order $n$, it was proved that $rc(G)\leq \lceil\frac n 2 \rceil$ and the bound is tight. In this paper, we prove that for a connected graph $G$ of order $n$ with cut vertices, $rc(G) \leq\frac{n+r-1} 2$, where $r$ is the number of blocks of $G$ with even orders, and the upper bound is tight. Moreover, we also obtain a tight upper bound for a bridgeless graph, i.e., a 2-edge-connected graph.

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.