Name
Abstract | ||
|---|---|---|
In this paper a random graph model GZN2,pd is introduced, which is a combination of fixed torus grid edges in (Z∕NZ)2
and some additional random ones. The random edges are called long, and the probability of having a long edge between vertices u,v∈(Z∕NZ)2 with graph distance d on the torus grid is pd=c∕Nd, where c is some constant. We show that, whp, the diameter D(GZN2,pd)=Θ(logN). Moreover, we consider a modified non-monotonous bootstrap percolation on GZN2,pd. We prove the presence of phase transitions in mean-field approximation and provide fairly sharp bounds on the error of the critical parameters. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.dam.2018.11.006 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Graph diameter,Degree distribution,Bootstrap percolation,Phase transitions | Discrete mathematics,Binary logarithm,Combinatorics,Random graph,Phase transition,Lattice (order),Vertex (geometry),Bootstrap percolation,Distance,Torus,Mathematics | Journal |
Volume | ISSN | Citations |
258 | 0166-218X | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Svante Janson | 1 | 1009 | 149.67 |
| Robert Kozma | 2 | 21 | 10.20 |
| M. Ruszinkó | 3 | 230 | 35.16 |
| Yury Sokolov | 4 | 50 | 2.57 |