Spanning forests and special numbers
- Authors: Deza E.I.1
-
Affiliations:
- Московский педагогический государственный университет
- Issue: Vol 221 (2023)
- Pages: 51-62
- Section: Статьи
- URL: https://journal-vniispk.ru/2782-4438/article/view/271317
- DOI: https://doi.org/10.36535/0233-6723-2023-221-51-62
- ID: 271317
Cite item
Full Text
Abstract
In this paper, we discuss enumerating some graphs of a special type. New results on the number of spanning forests of graphs playing an important role in information theory are obtained. We consider properties of convergent spanning forests of directed graphs involved in the construction of the quasi-metric of the mean time of the first pass, which is a generalized metric structure closely related to ergodic homogeneous Markov chains. We examine characteristics of spanning root forests and convergent spanning forests of directed and undirected graphs that are used for constructing the matrix of relative forest availability, which is one of the proximity measures of vertices of graphs. The reasonings are illustrated by several simple graph models, including a simple path, a simple cycle, a caterpillar graph, and their oriented analogs.
About the authors
E. I. Deza
Московский педагогический государственный университет
Author for correspondence.
Email: elena.deza@gmail.com
Russian Federation, Москва
References
- Воробьев Н. Н. Числа Фибоначчи. — М.: Наука, 1978.
- Деза Е. И., Мханна Б. О специальных свойствах некоторых квазиметрик// Чебышев. сб. — 2020. —21, №1. — С. 145–164.
- Деза Е. И., Мханна Б. Вопросы перечисления остовных лесов некоторых графов// Чебышев. сб. —2021. — 22, №3. — С. 77–99.
- Chebotarev P. A graph theoretic interpretation of the mean first passage times/ arXiv: math/0701359 [math.PR].
- Chebotarev P. Spanning forest and the Golden ratio// Discr. Appl. Math. — 2008. — 156. — P. 813–821.
- Chebotarev P., Agaev R. Forest matrices around the Laplacian matrix// Lin. Alg. Appl. — 2002. — 356.— P. 253–274.
- Chebotarev P., Deza E. Hitting time quasi-metric and its forest representation// Optim. Lett. — 2020. — 14.— P. 291–307.
- Chebotarev P. Yu., Shamis E. V. On proximity measures for graph vertices// Automat. Remote Control.— 1998. — 59. — P. 1443–1459.
- Deza M., Deza E., Vidali J. Cones of weighted and partial metrics// Proc. Int. Conf. on Algebra, 2010. —Hackensack, New Jersey: World Scientific, 2012. — P. 177–197.
- Kirkland S. J., Neumann M. Group Inverses of M-Matrices and Their Applications. — CRC Press, 2012.
- Leighton T., Rivest R. L. The Markov chain tree theorem. Computer Science Technical Report MIT/LCS/TM-249. — Cambridge, Massachusetts: Laboratory of Computer Science, MIT, 1983.
- Meyer C. D., Jr. The role of the group generalized inverse in the theory of finite Markov chains// SIAM Rev. — 1975. — 17. — P. 443–464.
Supplementary files
