Enumeration of labeled outerplanar bicyclic and tricyclic graphs
Vitalii Antonievich Voblyi, A. K. Meleshko · Journal of Applied and Industrial Mathematics · 2017
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 .