|
Diskretnyi Analiz i Issledovanie Operatsii, 2022, Volume 29, Issue 4, Pages 5–14 DOI: https://doi.org/10.33048/daio.2022.29.732
(Mi da1306)
|
|
|
|
This article is cited in 1 scientific paper (total 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
DOI:
https://doi.org/10.33048/daio.2022.29.732
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.
Received: 07.02.2022 Revised: 17.04.2022 Accepted: 19.04.2022
Citation:
V. A. Voblyi, “On asymptotical enumeration of labeled series-parallel $k$-cyclic graphs”, Diskretn. Anal. Issled. Oper., 29:4 (2022), 5–14; J. Appl. Industr. Math., 16:4 (2022), 853–859
Linking options:
https://www.mathnet.ru/eng/da1306 https://www.mathnet.ru/eng/da/v29/i4/p5
|
| Statistics & downloads: |
| Abstract page: | 193 | | Full-text PDF : | 63 | | References: | 65 | | First page: | 5 |
|