Enumeration of labeled thorn graphs
- Authors: Voblyi V.A.1, Arkhipova N.A.1
-
Affiliations:
- Всероссийский институт научной и технической информации Российской академии наук
- Issue: Vol 210 (2022)
- Pages: 49-54
- Section: Статьи
- URL: https://bakhtiniada.ru/2782-4438/article/view/270724
- DOI: https://doi.org/10.36535/0233-6723-2022-210-49-54
- ID: 270724
Cite item
Full Text
Abstract
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
About the authors
V. A. Voblyi
Всероссийский институт научной и технической информации Российской академии наук
Author for correspondence.
Email: vitvobl@yandex.ru
Russian Federation, Москва
N. A. Arkhipova
Всероссийский институт научной и технической информации Российской академии наук
Email: nataar1956@mail.ru
Russian Federation, Москва
References
- Бейтмен Г., Эрдейи А. Высшие трансцендентные функции. Т. 1. — М.: Наука, 1965.
- Бендер Э. А. Асимптотические методы в теории перечислений// в кн.: Перечислительные методы комбинаторного анализа. — М.: Мир, 1979. — С. 266-310.
- Воблый В. А. Асимптотическое перечисление помеченных связных разреженных графов с заданным числом висячих вершин// Дискр. анал. — 1985. — № 42. — С. 3-14.
- Воблый В. А. Асимптотическое перечисление графов некоторых типов/ Дисс. на соиск. уч. степ. канд. физ.-мат. наук — ВЦ АН СССР, 1985.
- Воблый В. А. О вероятности появления графа-гусеницы среди случайных разреженных графов// Тез. докл. II Всесоюз. конф. «Вероятностные методы в дискретной математике» (Петрозаводск). — Петрозаводск, 1988. — С. 25-26.
- Воблый В. А. О коэффициентах Райта и Степанова—Райта// Мат. заметки. — 1987. — 42,№6.— С. 854-862.
- Воблый В. А., Мелешко А. К. Перечисление помеченных колючих кактусов// Мат. XXIX Междунар. конф. КРОМШ-2018 (Симферополь, 17-29 сентября 2018 г.). — Симферополь: Полипринт, 2018. — С. 137-138.
- Медведев Ю. И., Ивченко Г. И. Асимптотическое представление конечных разностей от степенной функции в произвольной точке// Теор. вер. примен. — 1965. — 10, № 1. — С. 151-156.
- Bonchev D., Klein D. J. On the Wiener number of thorn trees, stars, rings, and rods// Croat. Chem. Acta. — 2002. — 75, № 2. — P. 613-620.
- Corless R. M., Gonnet G. H., Hare D. E., Jeffrey D. J., Knuth D. E. On the Lambert W -function// Adv. Comput. Math. — 1996. — 5, № 1. — P. 329-359.
- De N. Application of corona product graphs in computing topological indexes of some special chemical graphs// in: Handbook of Research on Applied Cybernetics and System Science. — IGI Global, 2017. — P. 82-101.
- El-Basil S. Applications of caterpillar trees in chemistry and physics// J. Math. Chem. — 1987. — 1.— P. 153-174.
- Harary F., Schwenk A. J. The number of caterpillars// Discr. Math. — 1973. — 6. — P. 359-365.
- Gutman I. Distance of thorny graphs// Publ. Inst. Math. Nouv. Ser. — 1998. — 63 (77). — P. 31-36.
- Pittel B., Wormald N. C. Counting connected graphs inside-out// J. Combin. Theory. Ser. B. — 2005. — 93, № 2. — P. 127-172.
- Wright E. M. Enumeration of smooth labelled graphs// Proc. Roy. Soc. Edinburgh. — 1982. — A91, № 3/4. — P. 205-212.
- Wright E. M. The number of connected sparsely edged graphs. II// J. Graph Theory. — 1978. — 2, № 4. — P. 299-305.
- Wright E. M. The number of connected sparsely edged graphs. III// J. Graph Theory. — 1980. — 4, № 4. — P. 393-407.
Supplementary files
