On the rainbow vertex-connection

A vertex-colored graph is {\it 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 {\it 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. Krivelevich and Yuster proved that if $G$ is a graph of order $n$ with minimum degree $\delta$, then $rvc(G)<11n\mathrm{/}\delta$. In this paper, we show that $rvc(G)\leq 3n/(\delta+1)+5$for$\delta\geq \sqrt{n-1}-1$and$n\geq 290$,while$rvc(G)\leq 4n/(\delta+1)+5$for$16\leq \delta\leq \sqrt{n-1}-2$and$rvc(G)\leq 4n/(\delta+1)+C(\delta)$for$6\leq\delta\leq 15$,where$C(\delta)=e^{\frac{3\log(\delta^3+2\delta^2+3)-3(\log 3-1)} {\delta-3}}-2$. We also prove that $rvc(G)\le 3n\mathrm{/}4-2$ for $\delta =3$, $rvc(G)\le 3n\mathrm{/}5-8\mathrm{/}5$ for $\delta =4$ and $rvc(G)\le n\mathrm{/}2-2$ for $\delta =5$. Moreover, an example shows that when $\delta \ge \sqrt{n-1}-1$ and $\delta =3,4,5$, our bounds are seen to be tight up to additive factors.