HomeIssuesThe number of labeled tetracyclic series-parallel blocks

The number of labeled tetracyclic series-parallel blocks | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 47. DOI: 10.17223/20710410/47/5

A series-parallel graph is a graph that does not contain as a hole a complete graph with four vertices. Such graphs are used in the construction of reliable communication networks. An explicit formula is obtained for the number of labeled series-parallel tetracyclic graphs with a given number of vertices. It is proved that with a uniform probability distribution, the probability that the labeled tetracyclic block is a series-parallel graph is asymptotically equal to 3/11.
Download file
Counter downloads: 92
  • Title The number of labeled tetracyclic series-parallel blocks
  • Headline The number of labeled tetracyclic series-parallel blocks
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 47
  • Date:
  • DOI 10.17223/20710410/47/5
Keywords
помеченный граф, тетрациклический граф, последовательнопараллельный граф, блок, перечисление, асимптотика, labeled graph, tetracyclic graph, series-parallel graph, block, enumeration, asymptotics
Authors
References
Bodirsky M., Gimenez O., Kang M., and Noy M. Enumeration and limit laws of series-parallel graphs // European J. Combinatorics. 2007. V. 28. P. 2091-2105
Radhavan S. Low-connectivity network design on series-parallel graphs // Networks. 2004. V. 43. No. 3. P. 163-176
Takamizawa K., Nishezeki T., and Saito N. Linear-time computability of combinatorial problems on series-parallel graphs // J. ACM. 1982. V. 29. No. 3. P. 623-641
Воблый В. А. Второе соотношение Риддела и следствия из него // Дискретн. анализ и исследование операций. 2019. Т. 26. №1. С. 20-32
Воблый В. А., Мелешко А. М. О числе помеченных последовательно-параллельных трициклических блоков // Материалы XV Междунар. конф. «Алгебра, теория чисел и дискретная геометрия. Современные проблемы и приложения». Тула: Изд-во ТПГУ, 2018. С. 168-170
Ford G. W. and Uhlenbeck G. E. Combinatorial problems in theory graphs. IV // Proc. Nat. Acad. Sci. USA. 1957. V. 43. P. 163-167
Степанов В. Е. О некоторых особенностях строения случайного графа вблизи критической точки // Теория вероятн. и ее применения. 1987. Т. 32. Вып. 4. С. 633-657
Heap B.R. Enumeration homeomorphically irreducible star graphs // J. Math. Phys. 1966. V. 7. No. 7. P. 1582-1587
Прудников А. П. и др. Интегралы и ряды. Т. 1. М.: Наука, ГРФМЛ, 1981. 800 с
Wright E.M. The number of connected sparsely edges graphs. II // J. Graph Theory. 1978. V. 2. P. 299-305
The number of labeled tetracyclic series-parallel blocks | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 47. DOI: 10.17223/20710410/47/5
The number of labeled tetracyclic series-parallel blocks | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 47. DOI: 10.17223/20710410/47/5
Download full-text version
Counter downloads: 315