To access the full text documents, please follow this link: http://hdl.handle.net/2117/104308

Title:	Asymptotic study of subcritical graph classes
Author:	Drmota, Michael; Fusy, Éric; Kang, Mihyun; Kraus, Veronika; Rué Perna, Juan José
Other authors:	Universitat Politècnica de Catalunya. Departament de Matemàtiques; Universitat Politècnica de Catalunya. MD - Matemàtica Discreta
Abstract:	We present a unified general method for the asymptotic study of graphs from the so-called subcritical graph classes, which include the classes of cacti graphs, outerplanar graphs, and series-parallel graphs. This general method works in both the labelled and unlabelled framework. The main results concern the asymptotic enumeration and the limit laws of properties of random graphs chosen from subcritical classes. We show that the number $g_n/n!$ (resp., $g_n$) of labelled (resp., unlabelled) graphs on n vertices from a subcritical graph class ${\mathcal{G}}=\cup_n {\mathcal{G}_n}$ satisfies asymptotically the universal behavior $g_n = c \!n^{-5/2} \!\gamma^n \! (1+o(1))$ for computable constants $c,\gamma$, e.g., $\gamma\approx 9.38527$ for unlabelled series-parallel graphs, and that the number of vertices of degree k (k fixed) in a graph chosen uniformly at random from $\mathcal{G}_n$ converges (after rescaling) to a normal law as $n\to\infty$.
Subject(s):	-Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs -Graph theory -Graph classes -Grafs, Teoria dels
Rights:	Attribution-NonCommercial-NoDerivs 3.0 Spain http://creativecommons.org/licenses/by-nc-nd/3.0/es/
Document type:	Article - Updated version Article
Share:

Show full item record