Enumeration of labeled outerplanar bicyclic and tricyclic graphs
- Authors: Voblyi V.A.1, Meleshko A.K.1
-
Affiliations:
- Bauman Moscow State Technical University
- Issue: Vol 11, No 2 (2017)
- Pages: 296-303
- Section: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/212752
- DOI: https://doi.org/10.1134/S1990478917020168
- ID: 212752
Cite item
Abstract
The class of outerplanar graphs is used for testing the average complexity of algorithms on graphs. A random labeled outerplanar graph can be generated by a polynomial algorithm based on the results of an enumeration of such graphs. By a bicyclic (tricyclic) graph we mean a connected graph with cyclomatic number 2 (respectively, 3). We find explicit formulas for the number of labeled connected outerplanar bicyclic and tricyclic graphs with n vertices and also obtain asymptotics for the number of these graphs for large n. Moreover, we obtain explicit formulas for the number of labeled outerplanar bicyclic and tricyclic n-vertex blocks and deduce the corresponding asymptotics for large n.
About the authors
V. A. Voblyi
Bauman Moscow State Technical University
Author for correspondence.
Email: vitvobl@yandex.ru
Russian Federation, Vtoraya Baumanskaya ul. 5, str. 1, Moscow, 105005
A. K. Meleshko
Bauman Moscow State Technical University
Email: vitvobl@yandex.ru
Russian Federation, Vtoraya Baumanskaya ul. 5, str. 1, Moscow, 105005