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

dmtcs:592 - Discrete Mathematics & Theoretical Computer Science, November 23, 2012, Vol. 14 no. 2 - https://doi.org/10.46298/dmtcs.592
Random graphs with bounded maximum degree: asymptotic structure and a logical limit lawArticle

Authors: Vera Koponen 1

  • 1 Department of Mathematics [Uppsala]

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.

https://doi.org/10.46298/dmtcs.592
Source: HAL:hal-00990599v1
Volume: Vol. 14 no. 2
Published on: November 23, 2012
Accepted on: June 9, 2015
Submitted on: March 12, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 318 times.
This article's PDF has been downloaded 299 times.