Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1017/S0963548314000248 | COMBINATORICS PROBABILITY & COMPUTING |
Keywords | Field | DocType |
mathematics | Discrete mathematics,Complete graph,Graph,Random regular graph,Combinatorics,Random graph,Giant component,Lipschitz continuity,Connectivity,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
23 | 4 | 0963-5483 |
Citations | PageRank | References |
0 | 0.34 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Louigi Addario-Berry | 1 | 127 | 22.22 |
| Svante Janson | 2 | 1009 | 149.67 |
| Colin McDiarmid | 3 | 1071 | 167.05 |