Upper Bound Involving Parameter σ2 for the Rainbow Connection Number
Tjklc Nankai · 2013
Let G be a connected graph of order n. The rainbow connection number rc(G) of G was introduced by Chartrand et al. Chandran et al. used the minimum degree δ of G and obtained an upper bound that rc(G) ≤ 3n/(δ + 1) + 3, which is tight up to additive factors. In this paper, we use the minimum degree-sum σ2 of G to obtain a better bound rc(G) ≤6nσ2+2+ 8, especially when δ is small(constant) but σ2is large(linear in n).