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

Rainbow connection numbers and the minimum degree sum of a graph

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

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 , the minimum degree sum of k independent vertices, to improve the upper bounds significantly. 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＋2k2）n/σk＋k＋5k if σk≤7k or σk≥8k, whereas rvc（G）≤（38k9＋2k2）n/σk＋k＋5k if 7kσk8k. Examples are given to show that our bounds are much better than the existing ones, i.e., for which δ is very small but σk is very large, and our bounds are rc（G）≤9k-3 and rvc（G）≤9k＋2k2 or rvc（G）≤83k/9＋2k2,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.