Premium
Resolvent of large random graphs
Author(s) -
Bordenave Charles,
Lelarge Marc
Publication year - 2010
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20313
Subject(s) - mathematics , indifference graph , cograph , chordal graph , bipartite graph , 1 planar graph , pathwidth , random graph , maximal independent set , combinatorics , discrete mathematics , resolvent , modular decomposition , random regular graph , odd graph , line graph , graph , pure mathematics
We analyze the convergence of the spectrum of large random graphs to the spectrum of a limit infinite graph. We apply these results to graphs converging locally to trees and derive a new formula for the Stieltjes transform of the spectral measure of such graphs. We illustrate our results on the uniform regular graphs, Erdös‐Rényi graphs and graphs with a given degree sequence. We give examples of application for weighted graphs, bipartite graphs and the uniform spanning tree of n vertices. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010