Computer Science – Computational Complexity
Scientific paper
2011-04-11
Computer Science
Computational Complexity
15 pages, 2 figures
Scientific paper
A path in an edge colored graph is said to be a rainbow path if no two edges on the path have the same color. An edge colored graph is (strongly) rainbow connected if there exists a (geodesic) rainbow path between every pair of vertices. The (strong) rainbow connectivity of a graph $G$, denoted by ($src(G)$, respectively) $rc(G)$ is the smallest number of colors required to edge color the graph such that the graph is (strong) rainbow connected. It is known that for \emph{even} $k$ to decide whether the rainbow connectivity of a graph is at most $k$ or not is NP-hard. It was conjectured that for all $k$, to decide whether $rc(G) \leq k$ is NP-hard. In this paper we prove this conjecture. We also show that it is NP-hard to decide whether $src(G) \leq k$ or not even when $G$ is a bipartite graph.
Ananth Prabhanjan
Nasre Meghana
No associations
LandOfFree
New Hardness Results in Rainbow Connectivity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with New Hardness Results in Rainbow Connectivity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New Hardness Results in Rainbow Connectivity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-730917