کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4627573 | 1631812 | 2014 | 4 صفحه PDF | دانلود رایگان |
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)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)rc(G) is an NP-hard problem, as well as that even deciding whether a graph has rc(G)=2rc(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.
Journal: Applied Mathematics and Computation - Volume 242, 1 September 2014, Pages 277–280