pith. sign in

arxiv: 1212.6115 · v1 · pith:2KWJDCPInew · submitted 2012-12-26 · 🧮 math.CO

Rainbow k-connectivity of random bipartite graphs

classification 🧮 math.CO
keywords graphrainbowpathrandombipartitecalledconnectivityedges
0
0 comments X
read the original abstract

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 $rc_k(G)$. For the random graph $G(n,p)$, He and Liang got a sharp threshold function for the property $rc_k(G(n,p))\leq d$. In this paper, we extend this result to the case of random bipartite graph $G(m,n,p)$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.