On the number of series parallel and outerplanar graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2005

On the number of series parallel and outerplanar graphs

Résumé

We show that the number $g_n$ of labelled series-parallel graphs on $n$ vertices is asymptotically $g_n \sim g \cdot n^{-5/2} \gamma^n n!$, where $\gamma$ and $g$ are explicit computable constants. We show that the number of edges in random series-parallel graphs is asymptotically normal with linear mean and variance, and that the number of edges is sharply concentrated around its expected value. Similar results are proved for labelled outerplanar graphs.
Fichier principal
Vignette du fichier
dmAE0174.pdf (146.02 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01184440 , version 1 (14-08-2015)

Identifiants

Citer

Manuel Bodirsky, Omer Gimenez, Mihyun Kang, Marc Noy. On the number of series parallel and outerplanar graphs. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.383-388, ⟨10.46298/dmtcs.3451⟩. ⟨hal-01184440⟩

Collections

INSMI TDS-MACS
71 Consultations
722 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More