Concentration of rainbow k-connectivity of a multiplex random graph

Shang, Yilun (2023) Concentration of rainbow k-connectivity of a multiplex random graph. Theoretical Computer Science, 951. p. 113771. ISSN 0304-3975

Preview	Text 1-s2.0-S0304397523000841-main.pdf - Published Version Available under License Creative Commons Attribution 4.0. Download (396kB) | Preview
Preview	Text rainbow k.pdf - Accepted Version Available under License Creative Commons Attribution 4.0. Download (124kB) | Preview

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.

Actions (login required)

View Item

Downloads