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

preprint2012arXivOpen access

Abstract

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

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.