Geodesic
The Number of Labeled Outerplanar $k$-Cyclic Graphs
Matematičeskie zametki, Tome 103 (2018) no. 5, pp. 657-666.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: enumeration, labeled graph, connected graph, $k$-cyclic graph, outerplanar graph, asymptotics.
Mots-clés : cactus 
@article{MZM_2018_103_5_a1,
     author = {V. A. Voblyi},
     title = {The {Number} of {Labeled} {Outerplanar} $k${-Cyclic} {Graphs}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {657--666},
     publisher = {mathdoc},
     volume = {103},
     number = {5},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2018_103_5_a1/}
}
TY  - JOUR
AU  - V. A. Voblyi
TI  - The Number of Labeled Outerplanar $k$-Cyclic Graphs
JO  - Matematičeskie zametki
PY  - 2018
SP  - 657
EP  - 666
VL  - 103
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2018_103_5_a1/
LA  - ru
ID  - MZM_2018_103_5_a1
ER  - 
%0 Journal Article
%A V. A. Voblyi
%T The Number of Labeled Outerplanar $k$-Cyclic Graphs
%J Matematičeskie zametki
%D 2018
%P 657-666
%V 103
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2018_103_5_a1/
%G ru
%F MZM_2018_103_5_a1
V. A. Voblyi. The Number of Labeled Outerplanar $k$-Cyclic Graphs. Matematičeskie zametki, Tome 103 (2018) no. 5, pp. 657-666. http://geodesic.mathdoc.fr/item/MZM_2018_103_5_a1/

[1] F. Kharari, Teoriya grafov, Mir, M., 1973 | MR | Zbl

[2] M. Bodirsky, O. Gimenez, M. Kang, M. Noy, “Enumeration and limit laws of series-parallel graphs”, European J. Combin., 28:8 (2007), 2091–2105 | DOI | MR

[3] M. Bodirsky, M. Kang, “Generating outerplanar graphs uniformly at random”, Combin. Probab. Comput., 15:3 (2006), 333–343 | DOI | MR

[4] M. Drmota, O. Giménez, M. Noy, “Vertices of given degree in series-parallel graphs”, Random Structures Algorithms, 36:3 (2010), 273–314 | DOI | MR

[5] A. de Meir, M. Noy, “On the maximum number of cycles in outerplanar and series-parallel graphs”, Graphs Combin., 28:3 (2012), 265–275 | DOI | MR

[6] V. A. Voblyi, “Ob odnoi formule dlya chisla pomechennykh svyaznykh grafov”, Diskretn. analiz i issled. oper., 19:4 (2012), 48–59 | MR

[7] V. A. Voblyi, “Prostaya formula dlya chisla pomechennykh vneshneplanarnykh $k$-tsiklicheskikh blokov”, Materialy XII Mezhdunarodnogo seminara “Diskretnaya matematika i ee prilozheniya”, Izd-vo Mosk. un-ta, M., 2016, 285–287

[8] V. A. Voblyi, “O perechislenii pomechennykh svyaznykh grafov s zadannymi chislami vershin i reber”, Diskretn. analiz i issled. oper., 23:2 (2016), 5–20 | DOI | MR

[9] Ya. Gulden, D. Dzhekson, Perechislitelnaya kombinatorika, Nauka, M., 1990 | MR | Zbl

[10] NIST Handbook of Mathematical Functions, Cambridge Univ. Press, Cambridge, 2010 | MR | Zbl

[11] Yu. A. Brychkov, Spetsialnye funktsii. Proizvodnye, integraly, ryady i drugie formuly. Spravochnik, Fizmatlit, M., 2006 | MR | Zbl

[12] E. M. Wright, “The number of connected sparsely edged graphs. III. Asymptotic results”, J. Graph Theory, 4:4 (1980), 393–407 | DOI | MR