Note on two results on the rainbow connection number of graphs

Details Note on two results on the rainbow connection number of graphs Note on two results on the rainbow connection number of graphs

2011-10-23

arxiv.org/abs/1110.5017v1

Mathematics

Combinatorics

4 pages

Scientific paper

An edge-colored graph $G$, where adjacent edges may be colored the same, is rainbow connected if any two vertices of $G$ are connected by a path whose edges have distinct colors. The rainbow connection number $rc(G)$ of a connected graph $G$ is the smallest number of colors that are needed in order to make $G$ rainbow connected. Caro et al. showed an upper bound $rc(G)\leq n-\delta$ for a connected graph $G$ of order $n$ with minimum degree $\delta$ in "On rainbow connection, Electron. J. Combin. 15(2008), R57". Recently, Shiermeyer gave it a generalization that $rc(G)\leq n- \frac{\sigma_2} 2$ in "Bounds for the rainbow connection number of graphs, Discuss. Math Graph Theory 31(2011), 387--395", where $\sigma_2$ is the minimum degree-sum. The proofs of both results are almost the same, both fix the minimum degree $\delta$ and then use induction on $n$. This short note points out that this proof technique does not work rigorously. Fortunately, Caro et al's result is still true but under our improved proof. However, we do not know if Shiermeyer's result still hold.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-526538