Том 28, номер 4, 2021 г., Стр. 61-69

УДК 519.175.3
Воблый В. А.
Асимптотическое перечисление помеченных последовательно-параллельных $k$-циклических графов без мостов

Аннотация:
Получена асимптотика для числа помеченных связных последовательно-параллельных $k$-циклических $n$-вершинных графов без мостов при большом числе вершин и фиксированном числе $k$. Доказывается, что почти все помеченные последовательно-параллельные $k$-циклические связные графы без мостов при фиксированном $k$ являются блоками.
Библиогр. 17.

Ключевые слова: перечисление, помеченный граф, блок, граф без мостов, последовательно-параллельный граф, $k$-циклический граф, асимптотика, случайный граф.

DOI: 10.33048/daio.2021.28.715

Воблый Виталий Антониевич ¹
1. Всероссийский институт научной и технической информации,
ул. Усиевича, 20, 125190, Москва, Россия
е-mail: vitvobl@yandex.ru

Статья поступила 10 мая 2021 г.
После доработки — 8 августа 2021 г.
Принята к публикации 16 августа 2021 г.

Литература

[1] Bodirsky M., Gimenez O., Kang M., Noy M. Enumeration and limit laws of series-parallel graphs // Eur. J. Comb. 2007. Vol. 28, No. 8. P. 2091–2105.

[2] Харари Ф. Теория графов. М.: Мир, 1973. 300 c.

[3] Mc Diarmid C., Scott A. Random graphs from a block stable class // Eur. J. Comb. 2016. Vol. 58. P. 96–106.

[4] Radhavan S. Low-connectivity network design on series-parallel graphs // Networks. 2004. Vol. 43, No. 3. P. 163–176.

[5] Воблый В. А. Второе соотношение Риддела и следствия из него // Дискрет. анализ и исслед. операций. 2019. Т. 26, № 1. С. 20–32.

[6] Воблый В. А. О перечислении помеченных последовательно-параллельных $k$-циклических 2-связных графов // Дискрет. анализ и исслед. операций. 2021. Т. 28, № 1. С. 5–14.

[7] Hanlon P., Robinson R. W. Counting bridgeless graphs // J. Comb. Theory, Ser. B. 1982. Vol. 33. P. 276–305.

[8] Воблый В. А. Перечисление помеченных бициклических и трициклических графов без мостов // Мат. заметки. 2012. Т. 91, вып. 2. С. 308–311.

[9] Воблый В. А. Об асимптотическом перечислении помеченных связных $k$-циклических графов без мостов // Мат. заметки. 2020. Т. 107, вып. 2. С. 304–306.

[10] Воблый В. А. О числе помеченных внешнепланарных $k$-циклических графов без мостов // Дискрет. анализ и исслед. операций. 2020. Т. 27, № 1. С. 5–16.

[11] Воблый В. А. О перечислении помеченных связных графов с заданными числами вершин и рёбер // Дискрет. анализ и исслед. операций. 2016. Т. 23, № 2. С. 5–20.

[12] Гульден Я., Джексон Д. Перечислительная комбинаторика, М.: Наука, 1990. 504 с.

[13] Риордан Дж. Комбинаторные тождества. М.: Наука, 1982. 256 с.

[14] Воблый В. А. Об одном подходе к перечислению помеченных связных графов: обзор результатов // Итоги науки и техники. Сер. Соврем. мат. прил. Темат. обзоры. 2020. Т. 188. С. 106–118.

[15] Титчмарш Е. Теория функций. М.: Наука, 1980. 464 с.

[16] Flajolet P. Analytic combinatorics. Cambridge: Camb. Univ. Press, 2009. 826 p.

[17] Wright E. M. The number of connected sparsely edged graphs. IV // J. Graph Theory. 1983. Vol. 7, No. 2. P. 219–229.