Перечисление помеченных колючих графов
- Авторы: Воблый В.А.1, Архипова Н.А.1
-
Учреждения:
- Всероссийский институт научной и технической информации Российской академии наук
- Выпуск: Том 210 (2022)
- Страницы: 49-54
- Раздел: Статьи
- URL: https://ogarev-online.ru/2782-4438/article/view/270724
- DOI: https://doi.org/10.36535/0233-6723-2022-210-49-54
- ID: 270724
Цитировать
Полный текст
Аннотация
Колючим графом называется связный граф, который становится гладким после однократного удаления висячих вершин вместе с инцидентными им ребрами. Получена явная формула для числа помеченных колючих графов с заданными числами вершин и ребер, а также найдена соответствующая асимптотика для числа таких графов с большим числом вершин. Доказывается, что при равномерном распределении вероятностей почти все помеченные связные разреженные графы не являются колючими графами.
Ключевые слова
Об авторах
Виталий Антониевич Воблый
Всероссийский институт научной и технической информации Российской академии наук
Автор, ответственный за переписку.
Email: vitvobl@yandex.ru
Россия, Москва
Наталия Александровна Архипова
Всероссийский институт научной и технической информации Российской академии наук
Email: nataar1956@mail.ru
Россия, Москва
Список литературы
- Бейтмен Г., Эрдейи А. Высшие трансцендентные функции. Т. 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.
Дополнительные файлы
