Upper bounds involving parameter $σ_2$ for the rainbow connection

Details Upper bounds involving parameter $σ_2$ for the rainbow connection Upper bounds involving parameter $σ_2$ for the rainbow connection

2011-01-17

arxiv.org/abs/1101.3119v1

Mathematics

Combinatorics

9 pages

Scientific paper

For a graph $G$, we define $\sigma_2(G)=min \{d(u)+d(v)| u,v\in V(G), uv\not\in 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)\leq 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)\leq 8\frac{n-2}{\sigma_2+2}+10 $ for $2\leq \sigma_2\leq 6, \sigma_2\geq 28 $, while for $ 7 \leq \sigma_2\leq 8, 16\leq \sigma_2\leq 27$, $ rvc(G)\leq \frac{10n-16}{\sigma_2+2}+10$, and for $9 \leq \sigma_2\leq 15, rvc(G)\leq \frac{10n-16}{\sigma_2+2}+A(\sigma_2)$ where $ A(\sigma_2)= 63,41,27,20,16,13,11,$ respectively.

Affiliated with

Also associated with

No associations

Rating

Upper bounds involving parameter $σ_2$ for the rainbow connection does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Upper bounds involving parameter $σ_2$ for the rainbow connection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Upper bounds involving parameter $σ_2$ for the rainbow connection will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-285177