Abstract
We consider a multiplex random graph G(n,m, p) with m independent color layers over a common vertex set V of order n. In each layer, the edges are independent following the Erd˝os-R´enyi model with edge probability p = c(ln n+ (k-1) ln ln n)/mn for some constant c > 1. A rainbow path in this context means a path with all edges from distinct layers. For a graph G G(n,m, p), let rck(G) be its rainbow k-connectivity, namely the smallest required number of layers so that any pair of vertices in G can be connected by k internally vertex disjoint rainbow paths. We show that with high probability, rck(G(n,m, p)) is concentrated on three consecutive numbers. These numbers are at distance Θ(ln n/(ln(ln n + (k-1)lnlnn))2) to the diameter of the graph.
Original language | English |
---|---|
Article number | 113771 |
Pages (from-to) | 1-11 |
Number of pages | 11 |
Journal | Theoretical Computer Science |
Volume | 951 |
Early online date | 10 Feb 2023 |
DOIs | |
Publication status | Published - 24 Mar 2023 |
Keywords
- Rainbow connectivity
- rainbow path
- multiplex network
- random graph