Rainbow k-connectivity of Random Bipartite Graphs

• DOI: 10.1007/s10255-020-0970-z
• Publication Date: 2020-12-27T16:02:31Z
• Authors: Xiao-lin Chen; Xue-liang Li; Hui-shu Lian
• Keywords: 0102 computer and information sciences; 01 natural sciences

A path in an edge-colored graph G is called a rainbow path if no two edges of the path are colored the same color. 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. For the random equi-bipartite graph G(n,n,p), Fujita et. al. got a sharp threshold function for the property rck(G(n,n,p)) ≤ 3. They also posed the following problem: For d ≥ 2, determine a sharp threshold function for the property rck(G) ≤ d, where G is another random graph model. This paper is to give a solution to their problem in the general random bipartite graph model G(m,n,p).