Name
Abstract | ||
|---|---|---|
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. |
Year | Venue | Keywords |
|---|---|---|
2011 | Clinical Orthopaedics and Related Research | computational complexity,bipartite graph,discrete mathematics,edge coloring |
Field | DocType | Volume |
Discrete mathematics,Edge coloring,Combinatorics,Edge-transitive graph,Graph power,Cubic graph,Petersen graph,Mathematics,Voltage graph,Complement graph,Path graph | Journal | abs/1104.2 |
Citations | PageRank | References |
5 | 0.94 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Prabhanjan Ananth | 1 | 234 | 18.43 |
| Meghana Nasre | 2 | 98 | 12.80 |