Abstract. We investigate the Laplacian eigenvalues of a random graph G(n, d) with a given expected degree distribution d. The main result is that w.h.p. G(n, d) has a large subgraph core(G(n, d)) such that the spectral gap of the normalized Laplacian of core( min with high probability; here c0 > 0 is a constant, anddmin signifies the minimum expected degree. The result in particular applies to sparse graphs withdmin = O(1) as n → ∞, and it is of interest in order to extend known spectral heuristics for random regular graphs to graphs with irregular degree distributions, e.g., power laws. The present paper complements the work of Chung, Lu, and Vu [Internet Mathematics 1, 2003].
In REF we studied the Laplacian eigenvalues of sparse random graphs with a given expected degree sequence.
The Spectral Gap of Random Graphs with Given Expected Degrees
ICALP (1)
Mathematics Computer Science