Том 27, номер 1, 2020 г., Стр. 5-16

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

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

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

DOI: 10.33048/daio.2020.27.653

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

Статья поступила 21 марта 2019 г.
После доработки — 9 октября 2019 г.
Принята к публикации 27 ноября 2019 г.

Литература

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

[2] Bodirsky M., Kang M. Generating outerplanar graphs uniformly at random // Comb., Probab., Comput. 2006. Vol. 15, No. 3. P. 333–343.

[3] 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.

[4] Drmota M., Fusy E., Kang M., Kraus V., Rue J. Asymptotic study of subcritical graph classes // SIAM J. Discrete Math. 2011. Vol. 25, No. 4. P. 1615–1651.

[5] Воблый В. А. Число помеченных внешнепланарных графов $k$-циклических графов // Мат. заметки. 2018. Т. 103, вып. 5. С. 657–666.

[6] Воблый В. А. Простая формула для числа помеченных внешнепланарных $k$-циклических блоков и их асимптотическое перечисление // Мат. XII Междунар. семинара «Дискретная математика и её приложения» (Москва, 20–25 июня 2016 г.). М.: МГУ, 2016. С. 285–287.

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

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

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

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

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

[12] Noy M. Random planar graphs and beyond // Proc. Int. Congress of Mathematicians. Seoul, 2014. Vol. IV. P. 407–431.

[13] Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977. 325 с.

[14] Воблый В. А. Перечисление помеченных эйлеровых кактусов // Мат. XI Междунар. семинара «Дискретная математика и её приложения» (Москва, 18–23 января 2012 г.). М.: МГУ, 2012. С. 275–277.