Nordhaus- gaddum-type bounds for the rainbow vertex-connection number of a graph

Abstract

A vertex-colored graph G is rainbow vertex-connected if any pair of distinct vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection number of G, denoted by rvc(G), is the minimum number of colors that are needed to make G rainbow vertex-connected. In this paper we give a Nordhaus-Gaddum-type result of the rainbow vertex-connection number. We prove that when G and Ḡ are both connected, then 2 < rvc(G) + rvc(Ḡ) ≤ n-1. Examples are given to show that both the upper bound and the lower bound are best possible for all n > 5.