A sharp upper bound for the rainbow 2-connection number of a 2-connected graph

摘要

A path in an edge-colored graph is called rainbow if no two edges of it are colored the same. For an ?-connected graph G and an integer k with 1≤k≤?, the rainbow k-connection number r~(ck)(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: What is the minimum constant >0 such that for every 2-connected graph G on n vertices, we have r~(c2)(G)≤n ? In this paper, we prove that the minimum constant =1 and r~(c2)(G)=n if and only if G is a cycle of order n, which solves the problem of Fujita et al.