Asymptotical Enumeration of Labeled Series-Parallel Tetracyclic Graphs

被引：0

作者：

V. A. Voblyi ^{[1
]}

机构：

[1] Russian Institute for Scientific and Technical Information of the Russian Academy of Sciences, Moscow

来源：

Journal of Mathematical Sciences | 2025年 / 287卷 / 5期

关键词：

05C30; asymptotics; enumeration; labeled graph; probability; series-parallel graph;

D O I：

10.1007/s10958-025-07635-1

中图分类号：

学科分类号：

摘要：

A series-parallel graph is a graph that does not contain a complete graph with four vertices as a minor. We find an asymptotics for the number of labeled connected series-parallel tetracyclic graphs with a large number of vertices. We prove that under a uniform probability distribution, the probability of the fact that a labeled connected tetracyclic graph is a series-parallel graph is asymptotically equal to 141/221. © The Author(s), under exclusive licence to Springer Nature Switzerland AG 2025.

引用

页码：716 / 720

页数：4

共 13 条

[1]

Bodirsky M., Gimenez O., Kang M., Noy M., Enumeration and limit laws of series-parallel graphs, Eur. J. Combin, 28, 8, pp. 2091-2105, (2007)

[2]

Goulden I.P., Jackson D.M., Combinatorial Enumeration, (1990)

[3]

McDiarmid C., Scott A., A random graphs from a block stable class, Eur. J. Combin, 58, pp. 96-106, (2016)

[4]

Radhavan S., Low-connectivity network design on series-parallel graphs, Networks, 43, 3, pp. 163-176, (2004)

[5]

Riordan J., Combinatorial Identities, (1968)

[6]

Voblyi V.A., On enumeration of labeled connected graphs with given numbers of vertices and edges, Diskr. Anal. Issled. Oper, 23, 2, pp. 5-20, (2016)

[7]

Voblyi V.A., The number of labeled outerplanar graphs of k-cyclic graphs, Mat. Zametki, 103, 5, pp. 657-666, (2018)

[8]

Voblyi V.A., Second Riddell relation and its consequences, Diskr. Anal. Issled. Oper, 26, 1, pp. 20-32, (2019)

[9]

Voblyi V.A., Enumeration of labeled serial-parallel tricyclic graphs”, Itogi Nauki Tekhn, Sovr. Mat. Prilozh. Temat. Obz, 177, pp. 132-136, (2020)

[10]

Voblyi V.A., The number of labeled serial-parallel tetracyclic blocks, Pricl. Diskr. Mat., No, 47, pp. 57-61, (2020)

← 1 2 →