RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2021 Volume 28, Issue 1, Pages 5–14 (Mi da1271)

This article is cited in 2 papers

On the enumeration of labeled series-parallel $k$-cyclic $2$-connected graphs

V. A. Voblyi

All-Russian Institute for Scientific and Technical Information of RAS 20 Usievich Street, 125190 Moscow, Russia

Abstract: We deduce an explicit formula for the number of labeled series-parallel $k$-cyclic $n$-vertex $2$-connected graphs and find the corresponding asymptotics for a large number of vertices and a fixed $k$. Under the uniform probability distribution, an asymptotic formula is obtained for the probability that a random $n$-vertex $k$-cyclic $2$-connected graph with a large number of vertices and a fixed $k$ is a series-parallel graph. Tab. 1, bibliogr. 11.

Keywords: enumeration, labeled graph, series-parallel graph, $k$-cyclic graph, asymptotics, random graph.

UDC: 519.175.3

Received: 11.06.2020
Revised: 20.10.2020
Accepted: 22.10.2020

DOI: 10.33048/daio.2021.28.693


 English version:
Journal of Applied and Industrial Mathematics, 2021, 15:1, 169–174

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025