×

The number of labeled tetracyclic series-parallel blocks. (Russian. English summary) Zbl 1455.05074

Summary: 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\).

MSC:

05C90 Applications of graph theory
05C30 Enumeration in graph theory
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
PDFBibTeX XMLCite
Full Text: DOI MNR

References:

[1] Bodirsky M., Gimenez O., Kang M., Noy M., “Enumeration and limit laws of series-parallel graphs”, European J. Combinatorics, 28 (2007), 2091-2105 · Zbl 1127.05052
[2] Radhavan S., “Low-connectivity network design on series-parallel graphs”, Networks, 43:3 (2004), 163-176 · Zbl 1053.90015
[3] Takamizawa K., Nishezeki T., Saito N., “Linear-time computability of combinatorial problems on series-parallel graphs”, J. ACM, 29:3 (1982), 623-641 · Zbl 0485.68055
[4] Voblyy V. A., “The second Riddell relation and its consequences”, Diskretn. analiz i issled. oper., 26:1 (2019), 20-32 (in Russian) · Zbl 1438.05132
[5] Voblyy V. A., Meleshko K. A., “On the number of labeled series-parallel tricyclic blocks”, Proc. Intern. Conf. “Algebra, Teoriya Chisel i Diskretnaya Geometriya. Sovremennyye Problemy i Prilozheniya”, TPSU Publ., Tula, 2018, 168-170 (in Russian)
[6] Ford G. W., Uhlenbeck G. E., “Combinatorial problems in theory graphs. IV”, Proc. Nat. Acad. Sci. USA, 43 (1957), 163-167
[7] Stepanov V. E., “On some features of the structure of a random graph near a critical point”, Teoriya Veroyatn. Primen., 32:4 (1987), 633-657 (in Russian) · Zbl 0637.60015
[8] Heap B. R., “Enumeration homeomorphically irreducible star graphs”, J. Math. Phys., 7:7 (1966), 1582-1587 · Zbl 0149.41401
[9] Prudnikov A. P. et al., Integrals and Series, v. 1, Nauka Publ., M., 1981, 800 pp. (in Russian)
[10] Wright E. M., “The number of connected sparsely edges graphs. II”, J. Graph Theory, 2 (1978), 299-305 · Zbl 0367.05042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.