2012/04/02 by Xueliang Li, Li, Xueliang, Sujuan Liu +1
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.1204.0392
A path in an edge-colored graph is called \em rainbow if no two edges of it are colored the same. For an ℓ-connected graph G and an integer k with 1≤ k≤ ℓ, the \em rainbow k-connection number rck(G) of G is defined to be the minimum number of colors required to color the edges of G such that every two distinct vertices of G are connected by at least k internally disjoint rainbow paths. Fujita et. al. proposed a problem that what is the minimum constant α>0 such that for all 2-connected graphs G on n vertices, we have rc2(G)≤ αn. In this paper, we prove that α=1 and rc2(G)=n if and only if G is a cycle of order n, settling down this problem.