2012/12/26 by Xiaolin Chen, Xueliang Li, Chen, Xiaolin +3
Mathematics · #05C15 #05C40 #05C80 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15 #msc:05C40 #msc:05C80
paper · pdf · doi:10.48550/arxiv.1212.6115
15 pages. arXiv admin note: text overlap with arXiv:1012.1942 by other authors
arxiv created 2012/12/26 · arxiv updated 2012/12/27
A path in an edge-colored graph G is called a rainbow path if no two edges of the path are colored the same. The minimum number of colors required to color the edges of G such that every pair of vertices are connected by at least k internally vertex-disjoint rainbow paths is called the rainbow k-connectivity of the graph G, denoted by rck(G). For the random graph G(n,p), He and Liang got a sharp threshold function for the property rck(G(n,p))≤ d. In this paper, we extend this result to the case of random bipartite graph G(m,n,p).