2009/06/22 by Xueliang Li, Li, Xueliang, Yuefang Sun +1 · 1 citation
Computer Science · Mathematics · #05C15 #05C40 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Interconnection Networks and Systems #cs.DM #math.CO #msc:05C15 #msc:05C40
paper · pdf · doi:10.48550/arxiv.0906.3946
9 pages
arxiv created 2009/06/22 · openalex publication_date 2009/06/22 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A path in an edge-colored graph G, where adjacent edges may be colored the same, is called a rainbow path if no two edges of G are colored the same. For a κ-connected graph G and an integer k with 1≤ k≤ κ, the rainbow k-connectivity rck(G) of G is defined as the minimum integer j for which there exists a j-edge-coloring of G such that every two distinct vertices of G are connected by k internally disjoint rainbow paths. Let G be a complete (ℓ+1)-partite graph with ℓ parts of size r and one part of size p where 0≤ p <r (in the case p=0, G is a complete ℓ-partite graph with each part of size r). This paper is to investigate the rainbow k-connectivity of G. We show that for every pair of integers k≥ 2 and r≥ 1, there is an integer f(k,r) such that if ℓ≥ f(k,r), then rck(G)=2. As a consequence, we improve the upper bound of f(k) from (k+1)2 to ck3/2+C, where 0<c<1, C=o(k3/2), and f(k) is the integer such that if n ≥ f(k) then rck(Kn)=2.