A new formula for the number of labeled series-parallel graphs (Q6190760)
From MaRDI portal
scientific article; zbMATH DE number 7800775
Language | Label | Description | Also known as |
---|---|---|---|
English | A new formula for the number of labeled series-parallel graphs |
scientific article; zbMATH DE number 7800775 |
Statements
A new formula for the number of labeled series-parallel graphs (English)
0 references
6 February 2024
0 references
\par In the introductory part, the author recollects the definition of a series-parallel graph and the origin of a formula for series-parallel graphs. \textit{M. Bodirsky} et al. [Eur. J. Comb. 28, No. 8, 2091--2105 (2007; Zbl 1127.05052)] determined an asymptotic formula for the number of labeled connected and double connected series-parallel graphs with a large number of vertices. \textit{V. A. Voblyi} [Prikl. Diskretn. Mat. 2020, No. 47, 57--61 (2020; Zbl 1455.05074)] and \textit{V. A. Voblyi} and \textit{A. M. Meleshko} [``On the number of labeled series-parallel tricyclic blocks'' (Russian), in: Proceedings of the XV international conference on algebra, number theory, and discrete mathematics. 168--170 (2018)] found the numbers of labeled series-parallel tricyclic and tetracyclic blocks with a given number of vertices. Also, Voblyi [loc. cit.] obtained an explicit formula for the number of labeled series-parallel \(k\)-cyclic blocks with a given number of vertices. In the paper, the author obtains a simpler explicit formula for the number of labeled series-parallel biconnected graphs with a given number of vertices. The author uses partial differentiation, expansion of an analytic function, Newton's binomial formula, Taylor expansion, and Maple software to obtain the formula for the number of labeled biconnected series-parallel graphs. The author takes the reader from simple and ordinary concepts to complex concepts in a logical way. Thus, there is a smooth flow in developing the paper. The paper is very concise and small. The detailed references given are appreciated. The standard of the paper is good.
0 references
enumeration
0 references
labeled graph
0 references
series-parallel graph
0 references
2-connected graph
0 references
explicit formula
0 references