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

Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2012, Vol. 14 no. 2 (2), pp.229--254
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990599
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 16:27:59
Dernière modification le : jeudi 7 septembre 2017 - 01:03:37
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:48:28

Fichier

2120-7552-5-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990599, version 1

Collections

Citation

Vera Koponen. Random graphs with bounded maximum degree: asymptotic structure and a logical limit law. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2012, Vol. 14 no. 2 (2), pp.229--254. 〈hal-00990599〉

Partager

Métriques

Consultations de la notice

190

Téléchargements de fichiers

190