On the rainbow vertex-connection

Abstract

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/\delta$. In this paper, we show that $rvc(G)\le 3n/(\delta +1)+5$ for $\delta \ge \sqrt{n-1}-1$ and $n\ge 290$, while $rvc(G)\le 4n/(\delta +1)+5$ for $16\le \delta \le \sqrt{n-1}-2$ and $rvc(G)\le 4n/(\delta +1)+C(\delta )$ for $6\le \delta \le 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/4-2$ for $\delta =3$, $rvc(G)\le 3n/5-8/5$ for $\delta =4$ and $rvc(G)\le n/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.

7 pages

References in corpus (1)

• Rainbow Connection Number and Connected Dominating Sets

Cited by in corpus (2)

• Rainbow vertex-connection number of 2-connected graphs
• Further hardness results on the rainbow vertex-connection number of graphs