Abstract | ||
---|---|---|
Let P(n,m) be a graph chosen uniformly at random from the class of all planar graphs on vertex set [n]:={1,…,n} with m=m(n) edges. We show that in the sparse regime, when m/n≤1, with high probability the maximum degree of P(n,m) takes at most two different values. In contrast, this is not true anymore in the dense regime, when m/n>1, where the maximum degree of P(n,m) is not concentrated on any subset of [n] with bounded size. |
Year | DOI | Venue |
---|---|---|
2022 | 10.1016/j.jctb.2022.05.005 | Journal of Combinatorial Theory, Series B |
Keywords | DocType | Volume |
Random graphs,Random planar graphs,Maximum degree,Balls into bins,Prüfer sequence | Journal | 156 |
ISSN | Citations | PageRank |
0095-8956 | 0 | 0.34 |
References | Authors | |
5 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mihyun Kang | 1 | 163 | 29.18 |
Michael Missethan | 2 | 0 | 0.34 |