A connected graph with a cyclomatic number k is said to be a k-cyclic graph. We obtain the formula for the number of labelled non-planar pentacyclic graphs with a given number of vertices, and find the asymptotics of the number of labelled connected planar tetracyclic and pentacyclic graphs with n vertices as n → ∞. We prove that under a uniform probability distribution on the set of graphs under consideration, the probability that the labelled tetracyclic graph is planar is asymptotically equal to 1089/1105, and the probability that the labeled pentacyclic graph is planar is asymptotically equal to 1591/1675.
Download file
Counter downloads: 4
- Title An asymptotics for the number of labelled planar tetracyclic and pentacyclic graphs
- Headline An asymptotics for the number of labelled planar tetracyclic and pentacyclic graphs
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 59
- Date:
- DOI 10.17223/20710410/59/4
Keywords
probability, asymptotics, enumeration, block, pentacyclic graph, tetracyclic graph, planar graph, labelled graphAuthors
References
Дмитриев Е.Ф. Перечисление отмеченных графов с данными структурными свойствами. Автореферат дис..канд. физ.-мат. наук. Институт математики АН БССР, Минск, 1986.
Воблый В.А. О перечислении помеченных связных графов с заданными числами вершин и ребер // Дискрет, анализ и исслед. операций. 2016. Т. 23. №2. С. 5-20.
Воблый В.А. Асимптотическое перечисление помеченных последователвно-параллелвных тетрациклических графов // Итоги науки и техн. Соврем, матем. и её прилож. Темат. обзоры. 2020. Т. 187. С. 31-35.
Wright Е.М. The number of connected sparsely edged graphs //j. Graph Theory. 1977. V. 1. No.4. P.317-330.
Риордан Дж. Комбинаторные тождества. М.: Наука, 1982. 256 с.
Гульден Я., Джексон Д. Перечислителвная комбинаторика. М.: Наука, 1990. 504 с.
Воблый В.А. Перечисление помеченных эйлеровых пентациклических графов j j Прикладная дискретная математика. 2020. №50. С. 87-92.
Воблый В.А. Об одном подходе к перечислению помеченных связных графов: обзор резулвтатов // Итоги науки и техн. Совр. матем. и её прилож. Темат. обзоры. 2020. Т. 188. С.106-118.
McDiarmid С. and Scott A. Random graphs from a block stable class // Europ. J.Combin. 2016. V. 58. P.96-106.
Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977. 324 с.
Харари Ф. Теория графов. М.: Мир, 1973. 300 с.
Воблый В.А. Перечисление помеченных непланарных пентациклических блоков // Итоги науки и техн. Соврем, матем. и её прилож. Темат. обзоры. 2021. Т. 193. С. 28-32.
Воблый В.А., Мелешко А. К. Перечисление помеченных непланарных тетрациклических графов // Материалы XVIII Междунар. семинара "Комбинаторные конфигурации и их приложения". Кировоград, 2016. С. 33-36.
Gimenez O. and Noy M. Asymptotic enumeration and limit laws of planar graphs //j. Amer. Math. Soc. 2009. V.92. No. 2. P.169-210.
Bender E.A., Gao Z., and Wormand N.C. The number of labeled 2-connected planar graphs // Electron. J.Combinatorics. 2002. No. 9. Article R43.
Schmidt F.R., Торре Е., and Cremers D. Efficient planar graphs cuts with applications in computer vision // IEEE Computer Society Conf.Computer Vision and Pattern Recognition. Miami, Florida, 2009. P. 1-6.
Карандашев Я. M., Малъсагов М. Ю. Полиномиальный алгоритм точного вычисления статистической суммы для модели бинарных спинов на планарных графах // Тр. НИ-пеп РАН. 2017. Т. 7. У1. с. 18-24.
Haymaker К. and О Pella J. Locally recoverable codes from planar graphs //j. Algebra Comb. Discrete Appl. 2020. V.7. No. 1. P.35-53.
Aggarwal A., Klawe M., and Shor Р. Multilayer grid embedding for VLSI // Algorirhmica. 1991. No. 6. P. 129-151.
Рихтер М. Р. Алгоритм трассировки при проектировании СБИС // Научно-технические ведомости СПбГПУ. 2011. Выл. 5. С. 111-118.
An asymptotics for the number of labelled planar tetracyclic and pentacyclic graphs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2023. № 59. DOI: 10.17223/20710410/59/4
Download full-text version
Counter downloads: 534