图的彩虹连通数与最小度和

令G是一个阶为n且最小度为δ的连通图. 当δ很小而n很大时, 现有的依据于最小度参数的彩虹边连通数和彩虹点连通数的上界都很大, 它们是n的线性函数. 本文中, 我们用另一种参数,即k个独立点的最小度和σ_k来代替δ, 从而在很大程度上改进了彩虹边连通数和彩虹点连通数的上界. 本文证明了如果G有k个独立点, 那么rc(GG)≤3kn/(σk+k)+6k-3. 同时也证明了下面的结果, 如果σ_k≤7k或σ_k≥8k, 那么rvc(G)≤(4k+2k²)n/(σ_k+k)+5k; 如果7k<σ_k<8k, 那么rvc(G)≤(38k/9+2k²)n/(σ_k+k)+5k.文中也给出了例子说明我们的界比现有的界更好, 即我们的界为rc(G)≤9k-3和rvc(G)≤9k+2k²或rvc(G)≤83k/9+2k², 这意味着当δ很小而σ_k很大时, 我们的界是一个常数, 而现有的界却是n的线性函数.

Rainbow connection numbers and the minimum degree sum of a graph

Let G be a connected graph with order n and minimum degree δ. The existing upper bounds of the rainbow connection number and the rainbow vertex-connection number in terms of the minimum degree are very large, linear in n, if δ is small and n is large. In this paper, we want to replace δ by another parameter σ_k+k, the minimum degree sum of k independent vertices, to improve the upper bounds signi cantly. We prove that if G is a connected graph of order n with k independent vertices, then rc(G)≤3kn/(σ_k+k)+6k-3. We also prove that rvc(G)≤(4k+2k²)n/(σ_k+k)+5k if σ_k≤7k or σ_k≥8k; whereas rvc(G)≤(38k/9+2k²)n/(σ_k+k)+5k if 7kk is very large, and our bounds are rc(G)≤9k-3 and rvc(G)≤9k+2k² or rvc(G)≤(83k/9)+2k², which imply that rc(G) and rvc(G) can be bounded by constants from our upper bounds, but linear in n from the existing ones.