Rainbow connection of graphs with diameter 2

Abstract

A path in an edge-colored graph $G$, where adjacent edges may have the same color, is called a rainbow path if no two edges of the path are colored the same. The rainbow connection number $rc(G)$ of $G$ is the minimum integer $i$ for which there exists an $i$-edge-coloring of $G$ such that every two distinct vertices of $G$ are connected by a rainbow path. It is known that for a graph $G$ with diameter 2, to determine $rc(G)$ is NP-hard. So, it is interesting to know the best upper bound of $rc(G)$ for such a graph $G$. In this paper, we show that $rc(G)\le 5$ if $G$ is a bridgeless graph with diameter 2, and that $rc(G)\le k+2$ if $G$ is a connected graph of diameter 2 with $k$ bridges, where $k\ge 1$.

10 pages

References in corpus (2)

• Rainbow Connection Number and Connected Dominating Sets
• Rainbow Connection Number and Radius

Cited by in corpus (6)

• New Hardness Results in Rainbow Connectivity
• Sharp upper bound for the rainbow connection number of a graph with diameter 2
• Rainbow connections for planar graphs and line graphs
• On a question on graphs with rainbow connection number 2
• Asymptotic value of the minimal size of a graph with rainbow connection number 2
• Online Rainbow Coloring In Graphs