Geodesic
Enumeration of labeled nonplanar pentacyclic blocks
Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the Voronezh spring mathematical school “Modern methods of the theory of boundary-value problems. Pontryagin readings – XXX”. Voronezh, May 3-9, 2019. Part 4, Tome 193 (2021), pp. 28-32.

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

An planar graph is a graph that can be drawn on a plane without intersecting edges. A pentacyclic graph is a connected graph with $n$ vertices and $n + 4$ edges. We obtain an explicit formula for the number of labeled nonplanar pentacyclic blocks with a given number of vertices and found the corresponding asymptotics for the number of such graphs with a large number of vertices. We prove that under the uniform probability distribution, the probability that the labeled pentacyclic block is a nonplanar graph is asymptotically equal to $80/539$.
Keywords: enumeration, labeled graph, block, planar graph, asymptotics, probability. 
@article{INTO_2021_193_a4,
     author = {V. A. Voblyi},
     title = {Enumeration of labeled nonplanar pentacyclic blocks},
     journal = {Itogi nauki i tehniki. Sovremenna\^a matematika i e\"e prilo\v{z}eni\^a. Temati\v{c}eskie obzory},
     pages = {28--32},
     publisher = {mathdoc},
     volume = {193},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/INTO_2021_193_a4/}
}
TY  - JOUR
AU  - V. A. Voblyi
TI  - Enumeration of labeled nonplanar pentacyclic blocks
JO  - Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory
PY  - 2021
SP  - 28
EP  - 32
VL  - 193
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/INTO_2021_193_a4/
LA  - ru
ID  - INTO_2021_193_a4
ER  - 
%0 Journal Article
%A V. A. Voblyi
%T Enumeration of labeled nonplanar pentacyclic blocks
%J Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory
%D 2021
%P 28-32
%V 193
%I mathdoc
%U http://geodesic.mathdoc.fr/item/INTO_2021_193_a4/
%G ru
%F INTO_2021_193_a4
V. A. Voblyi. Enumeration of labeled nonplanar pentacyclic blocks. Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the Voronezh spring mathematical school “Modern methods of the theory of boundary-value problems. Pontryagin readings – XXX”. Voronezh, May 3-9, 2019. Part 4, Tome 193 (2021), pp. 28-32. http://geodesic.mathdoc.fr/item/INTO_2021_193_a4/

[1] Bender E. A., “The number of labeled 2-connected planar graphs”, Electron. J. Combin., 9 (2002), R43 | DOI | MR | Zbl

[2] Voblyi V. A., Meleshko A. K., “Perechislenie pomechennykh neplanarnykh tetratsiklicheskikh grafov”, Mat. XVIII Mezhdunar. semin. «Kombinatornye konfiguratsii i ikh prilozheniya», Kirovograd, 2016, 33–36

[3] Dmitriev E. F., Perechislenie otmechennykh grafov s dannymi strukturnymi svoistvami, Avtoref. diss. na soisk. uch. step. kand. fiz.-mat. nauk, In-t mat. AN BSSR, Minsk, 1986

[4] Karandashev Ya. M., Malsagov M. Yu., “Polinomialnyi algoritm tochnogo vychisleniya statisticheskoi summy dlya modeli binarnykh spinov na planarnykh grafakh”, Tr. NIISI RAN., 7:1, 18–24 | MR

[5] Pechenkin V. V., GRIN — programmnoe obespechenie dlya sozdaniya, redaktirovaniya i issledovaniya grafov i setei, http://ecsocman.hse.ru/text/19282339

[6] Prudnikov A. P. i dr., Integraly i ryady, v. 1, Nauka, M., 1981 | MR

[7] Rikhter M. R., “Algoritm trassirovki pri proektirovanii SBIS”, Nauch.-tekhn. ved. SPbGPU., 2011, no. 5, 111–118

[8] Stepanov V. E., “O nekotorykh osobennostyakh stroeniya sluchainogo grafa vblizi kriticheskoi tochki”, Teor. veroyatn. primen., 32:4 (1987), 633–657 | MR

[9] Kharari F., Teoriya grafov, Mir, M., 1973

[10] Aggarwal A., Klawe M., Shor P., “Multilayer grid embedding for VLSI”, Algorirhmica., 6 (1991), 129–151 | DOI | MR | Zbl

[11] Ford G. W., Uhlenbeck G. E., “Combinatorial problems in theory graphs, IV”, Proc. Natl. Acad. Sci. U.S.A., 43 (1957), 163–167 | DOI | MR

[12] Haymaker K., O'Pella J., “Locally recoverable codes from planar graphs”, J. Algebra Comb. Discrete Appl., 7:1 (2020), 35–53 | MR | Zbl

[13] Heap B. R., “Enumeration homeomorphically irreducible star graphs”, J. Math. Phys., 7:7 (1966), 1582–1587 | DOI | MR | Zbl

[14] Schmidt F. R., Toppe E., Cremers D., “Efficient planar graphs cuts with applications in computer vision”, IEEE Computer Society Conf. on Computer Vision and Pattern Recognition (Miami, Florida), 2009, 1–6 | Zbl

[15] Wright E. M., “The number of connected sparsely edged graphs”, J. Graph Theory., 2:4 (1978), 299–305 | DOI | MR | Zbl