Elsevier, Applied Mathematics and Computation, (242), p. 277-280
DOI: 10.1016/j.amc.2014.05.066
Full text: Download
An edge-colored graph G is rainbow connected if every two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. It was proved that computing rc(G) is an NP-hard problem, as well as that even deciding whether a graph has rc(G) = 2 is NP-complete. Li et al. proved that rc(G) <= 5 if G is a bridgeless graph with diameter 2, while rc(G) <= 9 if G is a bridgeless graph with diameter 3. Furthermore, Uchizawa et al. showed that determining the rainbow connection number of graphs is strongly NP-complete even for outerplanar graphs. In this paper, we give upper bounds of the rainbow connection number of outerplanar graphs with small diameters.