Enumeration of labeled outerplanar bicyclic and tricyclic graphs |
| |
Authors: | V A Voblyi A K Meleshko |
| |
Institution: | 1.Bauman Moscow State Technical University,Moscow,Russia |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|