Том 29, номер 4, 2022 г., Стр. 5-14

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

Аннотация:
Получена асимптотика для числа помеченных связных последовательно-параллельных $k$-циклических $n$-вершинных графов при большом числе вершин и фиксированном числе $k$. Найдена вероятность того, что при равномерном вероятностном распределении случайный помеченный связный $n$-вершинный $k$-циклический граф при фиксированном $k$ и $n \to \infty$ является последовательно-параллельным графом. Кроме того, определена вероятность того, что случайный помеченный связный последовательно-параллельный $n$-вершинный $k$-циклический граф при фиксированном $k$ и $n \to \infty$ является кактусом.
Библиогр. 16.

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

DOI: 10.33048/daio.2022.29.732

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

Статья поступила 7 февраля 2022 г.
После доработки — 17 апреля 2022 г.
Принята к публикации 19 апреля 2022 г.

Литература

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

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

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

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

[5] Takamizawa K., Nishizeki T., Saito N. Linear-time computability of combinatorial problems on series-parallel graphs // J. ACM. 1982. V. 29, No. 3. P. 623–641.

[6] Воблый В. А. Перечисление помеченных последовательно-параллельных трициклических графов // Итоги науки и техники. Сер. Соврем. математика и её прил. Темат. обзор. Т. 177. М.: ВИНИТИ РАН, 2020. C. 132–136.

[7] Воблый В. А. Асимптотическое перечисление помеченных последовательно-параллельных тетрациклических графов // Итоги науки и техники. Сер. Соврем. математика и её прил. Темат. обзор. Т. 187. М.: ВИНИТИ РАН, 2020. C. 31–35.

[8] NIST handbook of mathematical functions. New York: Camb. Univ. Press, 2010. 951 p.

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

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

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

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

[13] Wright E. M. The number of connected sparsely edged graphs // J. Graph Theory. 1977. V. 1, No. 4. P. 317–330.

[14] Wright E. M. The number of connected sparsely edged graphs. II // J. Graph Theory. 1978. V. 2, No. 4. P. 299–305.

[15] Воблый В. А. Асимптотическое перечисление помеченных последовательно-параллельных $k$-циклических графов без мостов // Дискрет. анализ и исслед. операций. 2021. Т. 28, № 4. С. 61–69.

[16] Wright E. M. The number of connected sparsely edged graphs. III // J. Graph Theory. 1980. V. 4, No. 4. P. 393–407.