The complexity of determining the rainbow vertex-connection of graphs

Details The complexity of determining the rainbow vertex-connection of graphs The complexity of determining the rainbow vertex-connection of graphs

2011-01-17

arxiv.org/abs/1101.3126v1

Mathematics

Combinatorics

7 pages

Scientific paper

A vertex-colored graph is {\it rainbow vertex-connected} if any two vertices are connected by a path whose internal vertices have distinct colors, which was introduced by Krivelevich and Yuster. The {\it rainbow vertex-connection} of a connected graph $G$, denoted by $rvc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow vertex-connected. In this paper, we study the computational complexity of vertex-rainbow connection of graphs and prove that computing $rvc(G)$ is NP-Hard. Moreover, we show that it is already NP-Complete to decide whether $rvc(G)=2$. We also prove that the following problem is NP-Complete: given a vertex-colored graph $G$, check whether the given coloring makes $G$ rainbow vertex-connected.

Affiliated with

Also associated with

No associations

Rating

The complexity of determining the rainbow vertex-connection of graphs 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 The complexity of determining the rainbow vertex-connection of graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The complexity of determining the rainbow vertex-connection of graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-285224