Answers are grounded in this paper and cite their sources.
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)≤ 5 if G is a bridgeless graph with diameter 2, and that rc(G)≤ k+2 if G is a connected graph of diameter 2 with k bridges, where k≥ 1.
No takes yet. Share an insight, caveat, or question.
Li et al. (2011) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: