Geodesic
Enumeration of labeled thorn graphs
Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Geometry, Mechanics, and Differential Equations, Tome 210 (2022), pp. 49-54.

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

A thorn graph is a connected graph that becomes smooth after a single removal of end points together with their incident edges. An explicit formula is obtained for the number of labeled thorn graphs with given numbers of vertices and edges, and the corresponding asymptotics is found for the number of such graphs with a large number of vertices. It is proved that with a uniform probability distribution, almost all labeled connected sparse graphs are not thorn graphs.
Keywords: enumeration, labeled graph, thorn graph, asymptotics, probability. 
@article{INTO_2022_210_a5,
     author = {V. A. Voblyi and N. A. Arkhipova},
     title = {Enumeration of labeled thorn graphs},
     journal = {Itogi nauki i tehniki. Sovremenna\^a matematika i e\"e prilo\v{z}eni\^a. Temati\v{c}eskie obzory},
     pages = {49--54},
     publisher = {mathdoc},
     volume = {210},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/INTO_2022_210_a5/}
}
TY  - JOUR
AU  - V. A. Voblyi
AU  - N. A. Arkhipova
TI  - Enumeration of labeled thorn graphs
JO  - Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory
PY  - 2022
SP  - 49
EP  - 54
VL  - 210
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/INTO_2022_210_a5/
LA  - ru
ID  - INTO_2022_210_a5
ER  - 
%0 Journal Article
%A V. A. Voblyi
%A N. A. Arkhipova
%T Enumeration of labeled thorn graphs
%J Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory
%D 2022
%P 49-54
%V 210
%I mathdoc
%U http://geodesic.mathdoc.fr/item/INTO_2022_210_a5/
%G ru
%F INTO_2022_210_a5
V. A. Voblyi; N. A. Arkhipova. Enumeration of labeled thorn graphs. Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Geometry, Mechanics, and Differential Equations, Tome 210 (2022), pp. 49-54. http://geodesic.mathdoc.fr/item/INTO_2022_210_a5/

[1] Beitmen G., Erdeii A., Vysshie transtsendentnye funktsii. T. 1, Nauka, M., 1965 | MR

[2] Bender E. A., “Asimptoticheskie metody v teorii perechislenii”, Perechislitelnye metody kombinatornogo analiza, Mir, M., 1979, 266–310

[3] Voblyi V. A., “Asimptoticheskoe perechislenie pomechennykh svyaznykh razrezhennykh grafov s zadannym chislom visyachikh vershin”, Diskr. anal., 1985, no. 42, 3–14 | MR

[4] Voblyi V. A., Asimptoticheskoe perechislenie grafov nekotorykh tipov, Diss. na soisk. uch. step. kand. fiz.-mat. nauk, M., 1985 | Zbl

[5] Voblyi V. A., “O veroyatnosti poyavleniya grafa-gusenitsy sredi sluchainykh razrezhennykh grafov”, Tez. dokl. II Vsesoyuz. konf. «Veroyatnostnye metody v diskretnoi matematike» (Petrozavodsk), Petrozavodsk, 1988, 25–26

[6] Voblyi V. A., “O koeffitsientakh Raita i Stepanova—Raita”, Mat. zametki., 42:6 (1987), 854–862 | MR

[7] Voblyi V. A., Meleshko A. K., “Perechislenie pomechennykh kolyuchikh kaktusov”, Mat. XXIX Mezhdunar. konf. KROMSh-2018 (Simferopol, 17–29 sentyabrya 2018 g.), Poliprint, Simferopol, 2018, 137–138

[8] Medvedev Yu. I., Ivchenko G. I., “Asimptoticheskoe predstavlenie konechnykh raznostei ot stepennoi funktsii v proizvolnoi tochke”, Teor. ver. primen., 10:1 (1965), 151–156

[9] Bonchev D., Klein D. J., “On the Wiener number of thorn trees, stars, rings, and rods”, Croat. Chem. Acta., 75:2 (2002), 613–620

[10] Corless R. M., Gonnet G. H., Hare D. E., Jeffrey D. J., Knuth D. E., “On the Lambert $W$-function”, Adv. Comput. Math., 5:1 (1996), 329–359 | DOI | MR | Zbl

[11] De N., “Application of corona product graphs in computing topological indexes of some special chemical graphs”, Handbook of Research on Applied Cybernetics and System Science, IGI Global, 2017, 82–101 | MR

[12] El-Basil S., “Applications of caterpillar trees in chemistry and physics”, J. Math. Chem., 1 (1987), 153–174 | DOI | MR

[13] Harary F., Schwenk A. J., “The number of caterpillars”, Discr. Math., 6 (1973), 359–365 | DOI | MR | Zbl

[14] Gutman I., “Distance of thorny graphs”, Publ. Inst. Math. Nouv. Ser., 63 (77) (1998), 31–36 | MR | Zbl

[15] Pittel B., Wormald N. C., “Counting connected graphs inside-out”, J. Combin. Theory. Ser. B., 93:2 (2005), 127–172 | DOI | MR | Zbl

[16] Wright E. M., “Enumeration of smooth labelled graphs”, Proc. Roy. Soc. Edinburgh., A91:3/4 (1982), 205–212 | DOI | MR | Zbl

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

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