On the Enumeration of Labeled Series-Parallel k-Cyclic 2-Connected Graphs

被引：0

作者：

Voblyi V.A. ^{[1
]}

机构：

[1] All-Russian Institute for Scientific and Technical Information of Russian Academy ofSciences, Moscow

来源：

Journal of Applied and Industrial Mathematics | 2021年 / 15卷 / 01期

关键词：

asymptotics; enumeration; k-cyclic graph; labeled graph; random graph; series-parallel graph;

D O I：

10.1134/S1990478921010154

中图分类号：

学科分类号：

摘要：

Abstract: We deduce an explicit formula for the number of labeled series-parallel $$k$$-cyclic $$n$$-vertex $$2$$-connected graphs and find the correspondingasymptotics for a large number of vertices and a fixed $$k$$. Under the uniform probability distribution, anasymptotic formula is obtained for the probability that a random $$n$$-vertex $$k$$-cyclic $$2$$-connected graph with a large number of verticesand a fixed $$k$$ is a series-parallel graph. © 2021, Pleiades Publishing, Ltd.

引用

页码：169 / 174

页数：5

共 11 条

[1]

Bodirsky M., Gimenez O., Kang M., Noy M., Enumeration and Limit Laws of Series-Parallel Graphs, European J. Combin., 28, 8, pp. 2091-2105, (2007)

[2]

Radhavan S., Low-Connectivity Network Design on Series-Parallel Graphs, Networks, 43, 3, pp. 163-176, (2004)

[3]

Voblyi V.A., The Second Riddell Relation and Its Consequences, J. Appl. Ind. Math., 13, 1, pp. 168-174, (2019)

[4]

Voblyi V.A., Meleshko A.M., On the Number of Labeled Series-Parallel Tricyclic Blocks, Proceedings. XV International Conference ”Algebra, Number Theory, and Discrete Geometry. Current Problems and Applications”, pp. 168-170, (2018)

[5]

Voblyi V.A., The Number of Labeled Tetracyclic Series-Parallel Blocks, Prikl. Diskret. Mat. No., 47, pp. 57-61, (2020)

[6]

Lavrentyev M.A., Shabat B.V., Methods of the Theory of Functions of a Complex Variable, (1965)

[7]

Voblyi V.A., Explicit Formula for the Number of Labeled Series-Parallel k-Cyclic Blocks, Math. Notes, 108, 4, pp. 608-610, (2020)

[8]

(2020)

[9]

Charalambides C.A., Enumerative Combinatorics, (2002)

[10]

Medvedev Y.I., Ivchenko G.I., Asymptotic Representations of Finite Differences of a Power Function at an Arbitrary Point, Theory Probab. Appl., 10, 1, pp. 139-144, (1965)

← 1 2 →