Search

A series-parallel graph is a graph that does not contain a complete graph with four vertices as a minor. An explicit formula for the number of labeled series-parallel tricyclic graphs with a given number of vertices is obtained, and the corresponding asymptotics for the number of such graphs with a large number of vertices is found. We prove that under a uniform probability distribution, the probability that the labeled tricyclic graph is a series-parallel graph is asymptotically equal to 13/15. [ABSTRACT FROM AUTHOR]

A bi-block graph is a connected graph in which all blocks are complete bipartite graphs. Labeled bi-block graphs and bridgeless bi-block graphs are enumerated exactly and asymptotically by the number of vertices. It is proved that almost all labeled connected bi-block graphs have no bridges. In addition, planar bi-block graphs are enumerated, and an asymptotic estimate is found for the number of such graphs. [ABSTRACT FROM AUTHOR]

We derive an asymptotic formula for the number of labeled connected series-parallel -cyclic graphs of a large order with a fixed number . With a uniform probability distribution, we find the probability that a random labeled connected -vertex -cyclic graph with a fixed as is a series-parallel graph. In addition, we determine the probability that, with a uniform probability distribution, a random labeled connected series-parallel -vertex -cyclic graph with a fixed as is a cactus. [ABSTRACT FROM AUTHOR]

We deduce the asymptotics for the number of labeled connected series-parallel -cyclic graphs with large order and fixed number . We prove that almost all labeled series-parallel -cyclic connected graphs without bridges for fixed are blocks. [ABSTRACT FROM AUTHOR]

We deduce an explicit formula for the number of labeled series-parallel -cyclic -vertex -connected graphs and find the corresponding asymptotics for a large number of vertices and a fixed . Under the uniform probability distribution, an asymptotic formula is obtained for the probability that a random -vertex -cyclic -connected graph with a large number of vertices and a fixed is a series-parallel graph. [ABSTRACT FROM AUTHOR]

We obtain an explicit formula for the number of labeled connected outerplanar k-cyclic n-vertex bridgeless graphs. We find asymptotics for the number of those graphs for a large number of vertices and fixed k. As a consequence, we prove that, for k fixed, almost all labeled connected outerplanar k-cyclic graphs have bridges. [ABSTRACT FROM AUTHOR]

A k-cyclic graph is a graph with cyclomatic number k. An explicit formula for the number of labeled connected outerplanar k-cyclic graphs with a given number of vertices is obtained. In addition, such graphs with fixed cyclomatic number k and a large number of vertices are asymptotically enumerated. As a consequence, it is found that, for fixed k, almost all labeled connected outerplanar k-cyclic graphs with a large number of vertices are cacti. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We deduce a new formula for the number of labeled connected graphs with given order and number of edges in terms of the block generating function. Applying this formula, we exactly and asymptotically enumerate cacti with given order and cyclomatic number. [ABSTRACT FROM AUTHOR]