Abstract
We study the uniform random graph C-n with n vertices drawn from a subcritical class of connected graphs. Our main result is that the resealed graph C-n / root n converges to the Brownian continuum random tree T-e multiplied by a constant scaling factor that depends on the class under consideration. In addition, we provide sub-Gaussian tail bounds for the diameter D (C-n) and height H(C-n(center dot)) of the rooted random graph C-n(center dot) We give analytic expressions for the scaling factor in several cases, including for example the class of outerplanar graphs. Our methods also enable us to study first passage percolation on C-n, where we also show the convergence to T-e under an appropriate rescaling.
Item Type: | Journal article |
---|---|
Faculties: | Mathematics, Computer Science and Statistics > Mathematics |
Subjects: | 500 Science > 510 Mathematics |
ISSN: | 0091-1798 |
Language: | English |
Item ID: | 47394 |
Date Deposited: | 27. Apr 2018, 08:12 |
Last Modified: | 13. Aug 2024, 12:41 |