Rainbow vertex-connection number of 2-connected graphs

Abstract

The {\em rainbow vertex-connection number}, $rvc(G)$, of a connected graph $G$ is the minimum number of colors needed to color its vertices such that every pair of vertices is connected by at least one path whose internal vertices have distinct colors. In this paper we first determine the rainbow vertex-connection number of cycle $C_n$ of order $n\ge 3$, and then, based on it, prove that for any 2-connected graph $G$, $rvc(G)\le rvc(C_n)$, giving a tight upper bound for the rainbow vertex-connection. As a consequence, we show that for a connected graph $G$ with a block decomposition $B_1,B_2,...,B_k$ and $t$ cut vertices, $rvc(G)\le rvc(B_1)+rvc(B_2)+...+rvc(B_k)+t$.

10 pages

References in corpus (1)

• On the rainbow vertex-connection