Nordhaus-Gaddum-type theorem 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 $\bar{G}$ are both connected, then $2\le rvc(G)+rvc(\bar{G})\le n-1$. Examples are given to show that both the upper bound and the lower bound are best possible for all $n\ge 5$.

6 pages

Cited by in corpus (1)

• The vertex-rainbow index of a graph