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 conn...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 connec ted by at least k internally ver tex-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).展开更多
基金This paper is supported by the National Natural Science Foundation of China(Nos.11871034,11531011)by the Natural Science Foundation of Jiangsu Province(No.BK20150169).
文摘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 connec ted by at least k internally ver tex-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).
