Quesitions of enumeration of spanning forests of selected graphs

E. Deza ; B. Mhanna

Čebyševskij sbornik, Tome 22 (2021) no. 3, pp. 77-99.

Résumé

In this article we consider questions of graph enumeration for some graphs of a special form. In fact, a number of new results have been proved on the number of spanning trees and spanning forests of graphs that play an important role in the applied problems of Information Theory. On the one hand, the properties of the spanning converging forests of oriented graphs involved in the construction of the mean first passage time quasi-metric, a generalized metric structure closely related to ergodic homogeneous Markov chains, are considered. On the other hand, the characteristics of spanning rooted forests and spanning converging forests of non-oriented and oriented graphs needed for the construction of a matrix of relative connectivity via forests, one of the measures of proximity of the vertices of graph structures, which plays an important role in solving of applied problems, have been studied. The consideration is based on several simple graph models, including a simple cycle, a simple path and their oriented analogues. The first section (introduction) presents the history of the problem and provides an overview of the main ideas and results presented in the article. The role of graph models in the presentation and study of ergodic homogeneous Markov chains is considered. In fact, a Markov chain is a mathematical model of some random process describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. The Markov chain can be depicted as an oriented weighted graph of transitions whose vertices correspond to the states of the chain and the arcs correspond to the transitions between them. On the other hand, any connected graph can be used as a basis for building a model of the simplest Markov chain: if a vertex $i$ has degree $k$, all incident edges are converted into arcs with the weights $\frac{1}{k}$. The matrix of relative connectivity via forests for non-oriented and oriented graphs is defined; its role for solving important applied problems of Information Theory is disclosed. The second section contains the basic definitions of Graph Theory necessary to formulate and prove the main results of the article. The definitions of a graph and an oriented graph, a spanning subgraph, a spanning rooted forest (for non-orented graphs) and a spanning converging forest (for oriented graphs) are given. Some examples are represented. In the third section, the definition of Fibonacci numbers is given, a number of properties of Fibonacci numbers necessary to obtain the main results of the article for undirected paths and cycles are formulated and proved. In the fourth section, two theorems on the enumeration of graphs related to the construction of the mean first passage time matrix for a homogeneous ergodic Markov chain are proved. In fact, the number of spanning converging trees for the oriented path and the oriented cycle and the number of spanning rooted trees for the non-oriented path and the non-oriented cycle are given; the spanning forests consisting of two trees for the same graph structures are counted. Results for the oriented case are formulated in terms of values $2^k$, $k\geq 0$; results for the non-oriented case are formulated in terms of Fibonacci numbers $u_k$, $k\geq 1$. The proofs are based on elementary methods of enumerating Combinatorics. The fifth section presents the results related to enumeration of spanning forests needed for construction of the matrix of relative connectivity via forests for the non-oriented paths and cycles and their oriented analogues. Total number of spanning converging forests (for oriented paths and cycles) and total number of spanning rooted forests (for non-oriented paths and cycles) are found; enumeration of the spanning converging forests, in which a vertex $i$ belongs to a tree converging to a vertex $j$ (for the oriented paths and cycles), and enumeration of the spanning rooted forests, in which a vertex $i$ belongs to a tree with a root $j$ (for the non-oriented paths and cycles) are represented. As before, results for the oriented case are formulated in terms of values $2^k$, $ k\geq 0$; results for the non-oriented case are formulated in terms of Fibonacci numbers $u_k$, $ k\geq 1$. The sixth section (conclusion) presents the main conclusions of the article, outlines the ideas of further studies.

Détail

Keywords: graph, path, cycle, spanning converging forest of an oriented graph, spanning rooted forest of an non-oriented graph, Markov chain, mean first passage time, matrix of relative connectivity via forests.

Bibliographie

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

[2] Deza M.M., Deza E.I., Dyutur Sikirich M., “Poliedralnye konstruktsii, svyazannye s kvazi-metrikami”, Chebyshevskii sbornik, 16:2 (2015), 79–92 | MR | Zbl

[3] Deza E.I., Mkhanna B., “O spetsialnykh svoistvakh nekotorykh kvazimetrik”, Chebyshevskii sbornik, 21:1 (2020), 145–164 | MR | Zbl

[4] Potapov V.N., Teoriya informatsii. Kodirovanie diskretnykh veroyatnostnykh istochnikov, NGU, Novosibirsk, 1999

[5] Kharari F., Teoriya grafov, URSS, M., 2003

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

[7] Chebotarev P., “Spanning forest and the Golden ratio”, Discrete Applied Mathematics, 156 (2008), 813–821 | DOI | MR | Zbl

[8] Chebotarev P., “Studying new classes of graph metrics”, Proceedings of the SEE Conference "Geometric Science of Information", GSI-2013, Lecture Notes in Computer Science, 8085, eds. F. Nielsen, F. Barbaresco, 2013, 207–214 | DOI | MR | Zbl

[9] Chebotarev P., Agaev R., “Forest matrices around the Laplacian matrix”, Linear Algebra and its Applications, 356 (2002), 253–274 | DOI | MR | Zbl

[10] Chebotarev P., Deza E., “Hitting time quasi-metric and its forest representation”, Optimization Letters, 14 (2020), 291–307 | DOI | MR | Zbl

[11] Chebotarev P.Y., Shamis E.V., “On proximity measures for graph vertices”, Automation and Remote Control, 59 (1998), 1443–1459 | MR | Zbl

[12] Deza E., Deza M., Dutour Sikirić, Generalizations of Finite Metrics and Cuts, World Scientific, 2016 | MR | Zbl

[13] Deza M., Deza E., “Cones of partial metrics”, Contributions to Discrete Mathematics, 6 (2011), 26–47 | MR | Zbl

[14] Deza M. M., Deza E., Encyclopedia of Distances, Springer, Berlin–Heidelberg, 2016 | MR | Zbl

[15] Deza M., Deza E., Vidali J., “Cones of weighted and partial metrics”, Advances in Algebraic Structures, Proceedings of the Internat. Conference on Algebra (2010), 2012, 177–197 | MR | Zbl

[16] Kirkland S.J., Neumann M., Group inverses of M-matrices and their applications, CRC Press, 2012 | MR

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

[18] Meyer Jr., C. D., “The role of the group generalized inverse in the theory of finite Markov chains”, SIAM Review, 17 (1975), 443–464 | DOI | MR | Zbl

[19] Wilson W., “On quasi-metric spaces”, American Journal of Mathematics, 53 (1931), 675–684 | DOI | MR