On the diameter of random planar graphs
classification
🧮 math.CO
keywords
epsilonconnectedplanardiametergraphsprobabilityrandomconstant
read the original abstract
We show that the diameter D(G_n) of a random labelled connected planar graph with n vertices is equal to n^{1/4+o(1)}, in probability. More precisely there exists a constant c>0 such that the probability that D(G_n) lies in the interval (n^{1/4-\epsilon},n^{1/4+\epsilon}) is greater than 1-\exp(-n^{c\epsilon}) for {\epsilon} small enough and n>n_0(\epsilon). We prove similar statements for 2-connected and 3-connected planar graphs and maps.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.