uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
On the Spread of Random Graphs
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
2014 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 23, no 4, 477-504 p.Article in journal (Refereed) Published
Abstract [en]

The spread of a connected graph G was introduced by Alon, Boppana and Spencer [1], and measures how tightly connected the graph is. It is defined as the maximum over all Lipschitz functions f on V(G) of the variance of f(X) when X is uniformly distributed on V(G). We investigate the spread for certain models of sparse random graph, in particular for random regular graphs G(n,d), for Erdos-Renyi random graphs G(n,p) in the supercritical range p > 1/n, and for a `small world' model. For supercritical G(n,p), we show that if p = c/n with c > 1 fixed, then with high probability the spread of the giant component is bounded, and we prove corresponding statements for other models of random graphs, including a model with random edge lengths. We also give lower bounds on the spread for the barely supercritical case when p = (1 + o(1))/n. Further, we show that for d large, with high probability the spread of G(n, d) becomes arbitrarily close to that of the complete graph K-n.

Place, publisher, year, edition, pages
2014. Vol. 23, no 4, 477-504 p.
National Category
URN: urn:nbn:se:uu:diva-229429DOI: 10.1017/S0963548314000248ISI: 000338350900001OAI: oai:DiVA.org:uu-229429DiVA: diva2:736795
Available from: 2014-08-08 Created: 2014-08-07 Last updated: 2014-08-08Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Janson, Svante
By organisation
Department of Mathematics
In the same journal
Combinatorics, probability & computing

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 213 hits
ReferencesLink to record
Permanent link

Direct link