An Euler graph is a connected graph in which all degrees of vertices are even numbers. A pentacyclic graph is a connected graph with n vertices and n + 4 edges. We obtain an explicit formula for the number of labeled Euler pentacyclic graphs with a given number of vertices, and found the corresponding asymptotics for the number of such graphs with a large number of vertices. We prove that, given a uniform probability distribution, the probability that a labeled pentacyclic Euler graph is a block (cactus) is asymptotically 53/272 (63/272), respectively.
Download file
Counter downloads: 73
- Title Enumeration of labeled Eulerian pentacyclic graphs
- Headline Enumeration of labeled Eulerian pentacyclic graphs
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 50
- Date:
- DOI 10.17223/20710410/50/6
Keywords
labeled graph, Eulerian graph, pentacyclic graph, block, enumeration, asymptotics, probabilityAuthors
References
Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977. 324 с.
Kumar A. A study on Euler graph and it’s applications // Int. J. Math. Trends Technol. 2017. V. 43. No. 1. P.9-14.
Pancoska P., Moravek Z., and Moll U. M. Rational design of DNA sequences for nanotechnology, microarrays and molecular computers using Eulerian graphs // Nucleic Acids Res. 2004. V.32. No. 15. P.4630-4645.
Amudha P., Sagayaraj A. C. C., and Sheela A.C.S. An application of graph theory in cryptography // Int. J. Pure Appl. Math. 2018. V. 119. No. 13. P.375-383.
Read R. C. Euler graphs on labelled nodes // Canad. J. Math. 1962. V. 14. P.482-486.
Tazawa S. Enumeration of labelled 2-connected Euler graphs // J. Combinat. Inform. System Sci. 1998. V. 23. No. 1-4. P. 407-414.
Воблый В. А. Перечисление помеченных связных бициклических и трициклических эйлеровых графов // Матем. заметки. 2012. Т. 92. №5. С. 678-683.
Воблый В. А., Мелешко А. К. Перечисление помеченных эйлеровых тетрациклических графов //Дискретн. анализ и исслед. операций. 2014. Т. 21. №5. С. 17-22.
Воблый В. А. О числе помеченных эйлеровых пентациклических блоков //Материалы заочного семинара XIX Международ. конф. «Проблемы теоретической кибернетики». Казань, 2020. С. 41-44.
Воблый В. А. О перечислении помеченных связных графов с заданными числами вершин и ребер //Дискретн. анализ и исслед. операций. 2016. Т. 3. №2. С. 5-20.
Гульден Я., Джексон Д. Перечислительная комбинаторика. М.: Наука, 1990. 504с.
Риордан Дж. Комбинаторные тождества. М.: Наука, 1981. 256 с.
Воблый В. А. Второе соотношение Риддела и следствия из него // Дискретн. анализ и исслед. операций. 2019. Т. 26. №1. С. 20-32.
Mc Diarmid C. and Scott A. A random graphs from a block stable class. II //Europ. J. Combin. 2016. V. 58. P. 96-106.
Воблый В. А., Мелешко А. К. Перечисление помеченных полноблочно-кактусных графов // Дискретн. анализ и исслед. операций. 2014. Т. 21. №2. С. 24-32.
Enumeration of labeled Eulerian pentacyclic graphs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 50. DOI: 10.17223/20710410/50/6
Download full-text version
Counter downloads: 193