Том 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
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. |