RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive

Prikl. Diskr. Mat., 2020 Number 47, Pages 57–61 (Mi pdm694)

This article is cited in 8 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.

UDC: 519.175.3

DOI: 10.17223/20710410/47/5



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025