2011/01/17 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 #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1101.3119
openalex publication_date 2011/01/17 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
For a graph G, we define σ2(G)=min \d(u)+d(v)| u,v∈ V(G), uv\not∈ E(G)\, or simply denoted by σ2. A edge-colored graph is rainbow edge-connected if any two vertices are connected by a path whose edges have distinct colors, which was introduced by Chartrand et al. The rainbow connection of a connected graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow edge-connected. We prove that if G is a connected graph of order n, then rc(G)≤ 6(n-2)/(σ2+2)+7. Moreover, the bound is seen to be tight up to additive factors by a construction mentioned by Caro et al. A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors, which was recently introduced by Krivelevich and Yuster. The 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. We prove that if G is a connected graph of order n, then rvc(G)≤ 8(n-2)/(σ2+2)+10 for 2≤ σ2≤ 6, σ2≥ 28 , while for 7 ≤ σ2≤ 8, 16≤ σ2≤ 27, rvc(G)≤ (10n-16)/(σ2+2)+10, and for 9 ≤ σ2≤ 15, rvc(G)≤ (10n-16)/(σ2+2)+A(σ2) where A(σ2)= 63,41,27,20,16,13,11, respectively.