2011/02/25 by Jiu-Ying Dong, Xueliang Li, Dong, Jiuying +1
Computer Science · Mathematics · #05C15 #05C40 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1102.5149
openalex publication_date 2011/02/25 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
The rainbow connection number rc(G) and the rainbow vertex-connection number rvc(G) of a graph G were introduced by Chartrand et al. and Krivelevich and Yuster, respectively. Good upper bounds in terms of minimum degree δ were reported by Chandran et al., Krivelevich and Yuster, and Li and Shi. However, if a graph has a small minimum degree δ and a large number of vertices n, these upper bounds are very large, linear in n. Hence, one may think to look for a good parameter to replace δ and decrease the upper bounds significantly. Such a natural parameter is σk. In this paper, for the rainbow connection number we prove that if G is a connected graph of order n with k independent vertices, then rc(G)≤ 3k(n-2)/(σk+k)+6k-4. For the rainbow vertex-connection number, we prove that rvc(G)≤ \frac(4k+2k2)nσk+k+5k if σk≤ 7k and σk≥ 8k, and rvc(G)≤ \frac((38k)/(9)+2k2)nσk+k+5k if 7k