A Mathematical Model for the Rainbow Vertex-Connection Number

Abstract

The concept of rainbow connection was introduced by Chartrand et al. [2] in 2008. A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection of a connected graph G, denoted by rvc(G), is the minimum number of colors needed to make G rainbow vertex-connected. In this paper, we introduce the first mathematical model of the problem.