Rainbow k-connectivity of Random Bipartite Graphs

• 作者: Xiao-lin CHEN Xue-liang LI Hui-shu LIAN
• 来源期刊: 应用数学学报（英文版）
• 年，卷（期）: 2020,（4）
• 页码范围: 879-890
• 页数: 12页
• 语种: 英文

摘要

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).