2010/12/16 by Xueliang Li, Yongtang Shi, Li, Xueliang +1 · 1 citation
Computer Science · Mathematics · #05C15 #05C40 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1012.3504
openalex publication_date 2010/12/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A vertex-colored graph is \it rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors, which was introduced by Krivelevich and Yuster. The \it rainbow vertex-connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. Krivelevich and Yuster proved that if G is a graph of order n with minimum degree δ, then rvc(G)<11n/δ. In this paper, we show that rvc(G)≤ 3n/(δ+1)+5 for δ≥ √(n-1)-1 and n≥ 290, while rvc(G)≤ 4n/(δ+1)+5 for 16≤ δ≤ √(n-1)-2 and rvc(G)≤ 4n/(δ+1)+C(δ) for 6≤δ≤ 15, where C(δ)=e^\frac3log(δ3+2δ2+3)-3(log 3-1) δ-3-2. We also prove that rvc(G)≤ 3n/4-2 for δ=3, rvc(G)≤ 3n/5-8/5 for δ=4 and rvc(G)≤ n/2-2 for δ=5. Moreover, an example shows that when δ≥ √(n-1)-1 and δ=3,4,5, our bounds are seen to be tight up to additive factors.