Upper bounds involving parameter ${\sigma }_2$ for the rainbow connection

Abstract

For a graph $G$, we define ${\sigma }_2(G)=min\{d(u)+d(v)|u,v\in V(G),uv\notin E(G)\}$, or simply denoted by ${\sigma }_2$. A edge-colored graph is rainbow edge-connected if any two vertices are connected by a path whose edges have distinct colors, which was introduced by Chartrand et al. The rainbow connection of a connected graph $G$, denoted by $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow edge-connected. We prove that if $G$ is a connected graph of order $n$, then $rc(G)\le 6\frac{n-2}{{\sigma }_2+2}+7$. Moreover, the bound is seen to be tight up to additive factors by a construction mentioned by Caro et al. A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors, which was recently introduced by Krivelevich and Yuster. The 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. We prove that if $G$ is a connected graph of order $n$, then $rvc(G)\le 8\frac{n-2}{{\sigma }_2+2}+10$ for $2\le {\sigma }_2\le 6,{\sigma }_2\ge 28$, while for $7\le {\sigma }_2\le 8,16\le {\sigma }_2\le 27$, $rvc(G)\le \frac{10n-16}{{\sigma }_2+2}+10$, and for $9\le {\sigma }_2\le 15,rvc(G)\le \frac{10n-16}{{\sigma }_2+2}+A({\sigma }_2)$ where $A({\sigma }_2)=63,41,27,20,16,13,11,$ respectively.

9 pages