On the number of series parallel and outerplanar graphs
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...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2005-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3451/pdf |
| _version_ | 1797270383065300992 |
|---|---|
| author | Manuel Bodirsky Omer Gimenez Mihyun Kang Marc Noy |
| author_facet | Manuel Bodirsky Omer Gimenez Mihyun Kang Marc Noy |
| author_sort | Manuel Bodirsky |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:03:23Z |
| format | Article |
| id | doaj.art-d772594c99c540ffb4fa361c8f6cfcc1 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:03:23Z |
| publishDate | 2005-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-d772594c99c540ffb4fa361c8f6cfcc12024-03-07T14:41:15ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502005-01-01DMTCS Proceedings vol. AE,...Proceedings10.46298/dmtcs.34513451On the number of series parallel and outerplanar graphsManuel Bodirsky0Omer Gimenez1Mihyun Kang2Marc Noy3Department of Computer Science [Berlin]Departament de Matemàtica Aplicada IIDepartment of Computer Science [Berlin]Departament de Matemàtica Aplicada IIWe 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.https://dmtcs.episciences.org/3451/pdfanalytic combinatoricsnormal lawseries parallel graphouterplanar graphrandom graphasymptotic enumerationlimit law[info.info-dm] computer science [cs]/discrete mathematics [cs.dm][math.math-co] mathematics [math]/combinatorics [math.co] |
| spellingShingle | Manuel Bodirsky Omer Gimenez Mihyun Kang Marc Noy On the number of series parallel and outerplanar graphs Discrete Mathematics & Theoretical Computer Science analytic combinatorics normal law series parallel graph outerplanar graph random graph asymptotic enumeration limit law [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] |
| title | On the number of series parallel and outerplanar graphs |
| title_full | On the number of series parallel and outerplanar graphs |
| title_fullStr | On the number of series parallel and outerplanar graphs |
| title_full_unstemmed | On the number of series parallel and outerplanar graphs |
| title_short | On the number of series parallel and outerplanar graphs |
| title_sort | on the number of series parallel and outerplanar graphs |
| topic | analytic combinatorics normal law series parallel graph outerplanar graph random graph asymptotic enumeration limit law [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] |
| url | https://dmtcs.episciences.org/3451/pdf |
| work_keys_str_mv | AT manuelbodirsky onthenumberofseriesparallelandouterplanargraphs AT omergimenez onthenumberofseriesparallelandouterplanargraphs AT mihyunkang onthenumberofseriesparallelandouterplanargraphs AT marcnoy onthenumberofseriesparallelandouterplanargraphs |