Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647940 | Discrete Mathematics | 2013 | 5 Pages |
Abstract
A path in an edge-colored graph is called rainbow if no two edges of it are colored the same. For an ℓℓ-connected graph GG and an integer kk with 1≤k≤ℓ1≤k≤ℓ, the rainbow kk-connection number rck(G)rck(G) of GG is defined to be the minimum number of colors required to color the edges of GG such that every two distinct vertices of GG are connected by at least kk internally disjoint rainbow paths. Fujita et al. proposed a problem: What is the minimum constant α>0α>0 such that for every 2-connected graph GG on nn vertices, we have rc2(G)≤αnrc2(G)≤αn ? In this paper, we prove that the minimum constant α=1α=1 and rc2(G)=nrc2(G)=n if and only if GG is a cycle of order nn, which solves the problem of Fujita et al.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Xueliang Li, Sujuan Liu,