The complexity of determining the rainbow vertex-connection of a graph |
| |
Authors: | Lily Chen Xueliang Li Yongtang Shi |
| |
Affiliation: | Center for Combinatorics and LPMC-TJKLC, Nankai University, Tianjin 300071, China |
| |
Abstract: | A vertex-colored graph is 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 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 complexity of determining the rainbow vertex-connection of a graph 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. |
| |
Keywords: | Coloring Rainbow vertex-connection Computational complexity |
本文献已被 ScienceDirect 等数据库收录! |
|