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

Diskretn. Anal. Issled. Oper., 2022 Volume 29, Issue 4, Pages 5–14 (Mi da1306)

This article is cited in 1 paper

On asymptotical enumeration of labeled series-parallel $k$-cyclic graphs

V. A. Voblyi

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

Abstract: We deduce an asymptotic formula for the number of labeled connected series-parallel $k$-cyclic graphs with given order and fixed number $k$. Under uniform probability distribution, we find the probability that a random labeled connected $n$-vertex $k$-cyclic graph with a fixed $k$ and $n\to\infty$ is a series-parallel graph. In addition, we determine the probability that, under uniform probability distribution, a random labeled connected series-parallel $n$-vertex $k$-cyclic graph with a fixed $k$ and $n\to\infty$ is a cactus. Bibliogr. 16.

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

UDC: 519.175.3

Received: 07.02.2022
Revised: 17.04.2022
Accepted: 19.04.2022

DOI: 10.33048/daio.2022.29.732



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025