Discrete Mathematics & Theoretical Computer Science, Vol 14, No 2 (2012)

Font Size:  Small  Medium  Large

Random graphs with bounded maximum degree: asymptotic structure and a logical limit law

Vera Koponen


For any fixed integer R ≥2 we characterise the typical structure of undirected graphs with vertices 1, …, n and maximum degree R, as n tends to infinity. The information is used to prove that such graphs satisfy a labelled limit law for first-order logic. If R ≥5 then also an unlabelled limit law holds.

Full Text: PDF PostScript