|
This article is cited in 7 scientific papers (total in 7 papers)
Applied Graph Theory
The number of labeled tetracyclic series-parallel blocks
V. A. Voblyi All-Russian Institut for Scientific and Technical Information, Moscow, Russia
Abstract:
A series-parallel graph is a graph that does not contain a complete graph with four vertices as a minor. Such graphs are used in the construction of reliable communication networks. Let $TB(n)$ be the number of labeled series-parallel tetracyclic blocks with $n$ vertices. The formula $TB(n)=\dfrac{n!}{80640}(n^5+30n^4+257n^3+768n^2+960n+504)\dbinom{n-3}{3}$ is obtained. It is proved that with a uniform probability distribution, the probability that the labeled tetracyclic block is a series-parallel graph is asymptotically $3/11$.
Keywords:
labeled graph, tetracyclic graph, series-parallel graph, block, enumeration, asymptotics.
Citation:
V. A. Voblyi, “The number of labeled tetracyclic series-parallel blocks”, Prikl. Diskr. Mat., 2020, no. 47, 57–61
Linking options:
https://www.mathnet.ru/eng/pdm694 https://www.mathnet.ru/eng/pdm/y2020/i1/p57
|
Statistics & downloads: |
Abstract page: | 248 | Full-text PDF : | 61 | References: | 31 |
|