The Number of Labeled Outerplanar k-Cyclic Graphs

被引：0

作者：

Voblyi, V. A. ^{[1
]}

机构：

[1] Russian Acad Sci, All Russian Inst Sci & Tech Informat, Moscow, Russia

来源：

MATHEMATICAL NOTES | 2018年 / 103卷 / 5-6期

关键词：

enumeration; labeled graph; connected graph; k-cyclic graph; outerplanar graph; cactus; asymptotics; SERIES-PARALLEL GRAPHS;

D O I：

10.1134/S0001434618050024

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A k-cyclic graph is a graph with cyclomatic number k. An explicit formula for the number of labeled connected outerplanar k-cyclic graphs with a given number of vertices is obtained. In addition, such graphs with fixed cyclomatic number k and a large number of vertices are asymptotically enumerated. As a consequence, it is found that, for fixed k, almost all labeled connected outerplanar k-cyclic graphs with a large number of vertices are cacti.

引用

页码：694 / 702

页数：9

共 15 条

[1]

[Anonymous], 2010, NIST HDB MATH FUNCTI

[2]

[Anonymous], 1969, Graph Theory

[3] Generating outerplanar graphs uniformly at random [J].

Bodirsky, M ;

Kang, M .

COMBINATORICS PROBABILITY & COMPUTING, 2006, 15 (03) :333-343

[4] Enumeration and limit laws for series-parallel graphs [J].

Bodirsky, Manuel ;

Gimerez, Omer ;

Kang, Mihyun ;

Noy, Marc .

EUROPEAN JOURNAL OF COMBINATORICS, 2007, 28 (08) :2091-2105

[5]

Brychkov Y., 2008, Handbook of special functions: derivatives, integrals, series and other formulas

[6]

Brychkov YA, 2006, HDB SPECIAL FUNCTION

[7] On the Maximum Number of Cycles in Outerplanar and Series-Parallel Graphs [J].

de Mier, Anna ;

Noy, Marc .

GRAPHS AND COMBINATORICS, 2012, 28 (02) :265-275

[8] Vertices of Given Degree in Series-Parallel Graphs [J].

Drmota, Michael ;

Gimenez, Omer ;

Noy, Marc .

RANDOM STRUCTURES & ALGORITHMS, 2010, 36 (03) :273-314

[9]

Goulden I., 1983, COMBINATORIAL ENUMER

[10]

Goulden I. P., 1990, COMBINATORIAL ENUMER

← 1 2 →