Geodesic
Spanning forests and special numbers
Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the International Conference «Classical and Modern Geometry» dedicated to the 100th anniversary of the birth of Professor Levon Sergeyevich Atanasyan (July 15, 1921—July 5, 1998). Moscow, November 1–4, 2021. Part 2, Tome 221 (2023), pp. 51-62.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: graph, path, cycle, caterpillar graph, convergent spanning root forest of a directed graph, spanning root forest of an undirected graph, mean time of the first pass, relative forest accessibility matrix.
Mots-clés : Markov chain 
@article{INTO_2023_221_a5,
     author = {E. Deza},
     title = {Spanning forests and special numbers},
     journal = {Itogi nauki i tehniki. Sovremenna\^a matematika i e\"e prilo\v{z}eni\^a. Temati\v{c}eskie obzory},
     pages = {51--62},
     publisher = {mathdoc},
     volume = {221},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/INTO_2023_221_a5/}
}
TY  - JOUR
AU  - E. Deza
TI  - Spanning forests and special numbers
JO  - Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory
PY  - 2023
SP  - 51
EP  - 62
VL  - 221
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/INTO_2023_221_a5/
LA  - ru
ID  - INTO_2023_221_a5
ER  - 
%0 Journal Article
%A E. Deza
%T Spanning forests and special numbers
%J Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory
%D 2023
%P 51-62
%V 221
%I mathdoc
%U http://geodesic.mathdoc.fr/item/INTO_2023_221_a5/
%G ru
%F INTO_2023_221_a5
E. Deza. Spanning forests and special numbers. Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the International Conference «Classical and Modern Geometry» dedicated to the 100th anniversary of the birth of Professor Levon Sergeyevich Atanasyan (July 15, 1921—July 5, 1998). Moscow, November 1–4, 2021. Part 2, Tome 221 (2023), pp. 51-62. http://geodesic.mathdoc.fr/item/INTO_2023_221_a5/

[1] Vorobev N. N., Chisla Fibonachchi, Nauka, M., 1978

[2] Deza E. I., Mkhanna B., “O spetsialnykh svoistvakh nekotorykh kvazimetrik”, Chebyshev. sb., 21:1 (2020), 145–164

[3] Deza E. I., Mkhanna B., “Voprosy perechisleniya ostovnykh lesov nekotorykh grafov”, Chebyshev. sb., 22:3 (2021), 77–99

[4] Chebotarev P., A graph theoretic interpretation of the mean first passage times, arXiv: math/0701359 [math.PR]

[5] Chebotarev P., “Spanning forest and the Golden ratio”, Discr. Appl. Math., 156 (2008), 813–821

[6] Chebotarev P., Agaev R., “Forest matrices around the Laplacian matrix”, Lin. Alg. Appl., 356 (2002), 253–274

[7] Chebotarev P., Deza E., “Hitting time quasi-metric and its forest representation”, Optim. Lett., 14 (2020), 291–307

[8] Chebotarev P. Yu., Shamis E. V., “On proximity measures for graph vertices”, Automat. Remote Control., 59 (1998), 1443–1459

[9] Deza M., Deza E., Vidali J., “Cones of weighted and partial metrics”, Proc. Int. Conf. on Algebra, 2010, World Scientific, Hackensack, New Jersey, 2012, 177–197

[10] Kirkland S. J., Neumann M., Group Inverses of M-Matrices and Their Applications, CRC Press, 2012

[11] Leighton T., Rivest R. L., The Markov chain tree theorem. Computer Science Technical Report MIT/LCS/TM-249, Laboratory of Computer Science, MIT, Cambridge, Massachusetts, 1983

[12] Meyer C. D., Jr., “The role of the group generalized inverse in the theory of finite Markov chains”, SIAM Rev., 17 (1975), 443–464