Note on rainbow connection number of dense graphs

Details Note on rainbow connection number of dense graphs Note on rainbow connection number of dense graphs

2011-10-05

arxiv.org/abs/1110.1268v1

Mathematics

Combinatorics

4 pages

Scientific paper

An edge-colored graph $G$ is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph $G$, denoted by $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. Following an idea of Caro et al., in this paper we also investigate the rainbow connection number of dense graphs. We show that for $k\geq 2$, if $G$ is a non-complete graph of order $n$ with minimum degree $\delta (G)\geq \frac{n}{2}-1+log_{k}{n}$, or minimum degree-sum $\sigma_{2}(G)\geq n-2+2log_{k}{n}$, then $rc(G)\leq k$; if $G$ is a graph of order $n$ with diameter 2 and $\delta (G)\geq 2(1+log_{\frac{k^{2}}{3k-2}}{k})log_{k}{n}$, then $rc(G)\leq k$. We also show that if $G$ is a non-complete bipartite graph of order $n$ and any two vertices in the same vertex class have at least $2log_{\frac{k^{2}}{3k-2}}{k}log_{k}{n}$ common neighbors in the other class, then $rc(G)\leq k$.

Affiliated with

Also associated with

No associations

Rating

Note on rainbow connection number of dense graphs 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 Note on rainbow connection number of dense graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Note on rainbow connection number of dense graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-326038