Sandwiching a densest subgraph by consecutive cores1. Issue 2 (10th April 2014) - Gao, Pu
Abstract In this paper, we show that in the random graph G(n, c/n), with high probability, there exists an integer k˜ such that a subgraph of G(n, c/n), whose vertex set differs from a densest subgraph of G(n, c/n) by O(log2n) vertices, is sandwiched by the k˜ and the (k˜+1)‐core, for almost all sufficiently large c. We determine the value of k˜. We also prove that (a), the threshold of the k‐core being balanced coincides with the threshold that the average degree of the k‐core is at most 2(k−1), for all sufficiently large k; (b) with high probability, there is a subgraph of G(n, c/n) whose density is significantly denser than any of its nonempty cores, for almost all sufficiently large c > 0. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 341–360, 2015