Rainbow connection number of dense graphs

Details Rainbow connection number of dense graphs Rainbow connection number of dense graphs

2011-10-26

arxiv.org/abs/1110.5772v1

Mathematics

Combinatorics

8 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 $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. In this paper we show that $rc(G)\leq 3$, if $|E(G)|\geq {{n-2}\choose 2}+2$, and $rc(G)\leq 4$, if $|E(G)|\geq {{n-3}\choose 2}+3$. These bounds are sharp.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-717072