2010/04/14 by Xueliang Li, Li, Xueliang, Yuefang Sun +1
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 #Graph theory and applications #Interconnection Networks and Systems #cs.DM #math.CO #msc:05C15 #msc:05C40
paper · pdf · doi:10.48550/arxiv.1004.2312
6 pages
arxiv created 2010/04/14 · openalex publication_date 2010/04/14 · arxiv updated 2010/04/15 · 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 the path 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 any two distinct vertices of G are connected by k internally disjoint rainbow paths. Denote by Kr,r an r-regular complete bipartite graph. Chartrand et al. in "G. Chartrand, G.L. Johns, K.A. McKeon, P. Zhang, The rainbow connectivity of a graph, Networks 54(2009), 75-81" left an open question of determining an integer g(k) for which the rainbow k-connectivity of Kr,r is 3 for every integer r≥ g(k). This short note is to solve this question by showing that rck(Kr,r)=3 for every integer r≥ 2k\lceil(k)/(2)\rceil, where k≥ 2 is a positive integer.