Published in

Elsevier, Applied Mathematics and Computation, (242), p. 277-280

DOI: 10.1016/j.amc.2014.05.066

Links

Tools

Export citation

Search in Google Scholar

Rainbow connections for outerplanar graphs with diameter 2 and 3

Journal article published in 2014 by Xiaolong Huang, Xueliang Li, Yongtang Shi ORCID, Jun Yue, Yan Zhao
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Red circle
Postprint: archiving forbidden
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

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.