|
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
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→∞ 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→∞ 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
Linking options:
https://www.mathnet.ru/eng/da1306 https://www.mathnet.ru/eng/da/v29/i4/p5
|
Statistics & downloads: |
Abstract page: | 127 | Full-text PDF : | 34 | References: | 38 | First page: | 5 |
|