Том 28, номер 1, 2021 г., Стр. 5-14

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

Аннотация:
Получена явная формула для числа помеченных последовательно-параллельных $k$-циклических $n$-вершинных 2-связных графов, а также найдена соответствующая асимптотика при большом числе вершин и фиксированном числе $k$. При равномерном распределении вероятностей найдена асимптотическая формула для вероятности того, что случайный $k$-циклический $n$-вершинный 2-связный граф с большим числом вершин при фиксированном числе $k$ является последовательно-параллельным графом.
Табл. 1, библиогр. 11.

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

DOI: 10.33048/daio.2021.28.693

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

Статья поступила 11 июня 2020 г.
После доработки — 20 октября 2020 г.
Принята к публикации 22 октября 2020 г.

Литература

[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] Radhavan S. Low-connectivity network design on series-parallel graphs // Networks. 2004. Vol. 43, No. 3. P. 163–176.

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

[4] Воблый В. А., Мелешко А. М. О числе помеченных последовательно-параллельных трициклических блоков // Мат. XV Междунар. конф. «Алгебра, теория чисел и дискретная геометрия. Современные проблемы и приложения» (Тула, Россия, 28–31 мая 2018 г.). Тула: Изд-во ТГПУ, 2018. С. 168–170.

[5] Воблый В. А. Число помеченных последовательно-параллельных тетрациклических блоков // Прикл. дискрет. математика. 2020. № 47. С. 57–61.

[6] Лаврентьев М. А., Шабат Б. В. Методы теории функций комплексного переменного. М.: Наука, 1965. 716 с.

[7] Воблый В. А. Явная формула для числа помеченных последовательно-параллельных $k$-циклических блоков // Мат. заметки. 2020. Т. 108, вып. 4. С. 622–624.

[8] The on-line encyclopedia of integer sequences. Highland Park, NJ: The OEIS Foundation, 2020. Available at http://oeis.org (accessed Oct. 27, 2020).

[9] Charalambides C. A. Enumerative combinatorics. Boca Raton, FL: CRC Press, 2002. 609 p.

[10] Медведев Ю. И., Ивченко Г. И. Асимптотическое представление конечных разностей от степенной функции в произвольной точке // Теория вероятностей и её применения. 1965. Т. 10, № 1. С. 151–156.

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