Quesitions of enumeration of selected classes of oriented and non-oriented trees and forests

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 a simple graph model, so-called  caterpillar,  and its oriented analogues. The other simple graph models, including oriented and non-oriented simple cycles  and simple paths, where considered before.

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.
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-oriented graphs) and a spanning converging forest (for oriented graphs) are given. Some examples are represented (simple path, simple cycle, caterpillar and their oriented analogues).
In the same section a number of properties of Fibonacci numbers necessary to obtain the main results of the article for the undirected case is formulated.

In the third 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 caterpillar  and the number of spanning rooted trees for the non-oriented caterpillar 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 fourth 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 caterpillar and its oriented analogue. Total number of spanning converging forests (for oriented caterpillar) and total number of spanning rooted forests (for non-oriented caterpillar) 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 caterpillar), and enumeration of the spanning rooted forests, in which a vertex $i$ belongs to a tree with a root $j$ (for the non-oriented caterpillar) 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 fifth section contains the examples of the the matrix of relative connectivity via  forests.

The sixth section  (conclusion) presents the main conclusions of the article, outlines the ideas of further studies.

1. Vorobev, N.N. 1978, ”Fibonacci numbers“, M.: Nauka.

2. Deza, M.M., Deza, E.I., Dutour Sikiri´c, М. 2015, ”Polyhedral structures associated with quasimetrics“,

3. Chebyshevskii sbornik, Vol. 16 (2), P. 79 – 92.

4. Deza, E., Mhanna, B. ”On special properties of some special quasi-metrics“, Chebyshevskii

5. sbornik, Vol. 21 (1), P. 145 – 164.

6. Deza, E., Mhanna, B. ”Quasi-metrics on graphs“, Chebyshevskii sbornik, Vol. 22 (1), P. 48 – 75.

7. Deza, E., Mhanna, B. ”Question of enumeration of spanning forests of some graphs“,

8. Chebyshevskii sbornik, Vol. 22 (3), P. 77 – 99.

9. Potapov, V.N. 1999, ”Information Theory. Coding of discrete probabilistic sources“, Novosibirsk:

10. NSU center.

11. Harari, F. 2003, ”Graph Theory“, M.: URSS.

12. Chebotarev, P. 2008, ”Spanning forest and the Golden ratio“, Discrete Applied Mathematics,

13. Vol. 156, P. 813 – 821.

14. Chebotarev, P. 2013, ”Studying new classes of graph metrics“, in F. Nielsen and F. Barbaresco,

15. editors, Proceedings of the SEE Conference ”Geometric Science of Information“ (GSI-2013),

16. Lecture Notes in Computer Science, LNCS 8085, P. 207–214.

17. Chebotarev, P., Agaev, R. 2002, ”Forest matrices around the Laplacian matrix“, Linear Algebra

18. and its Applications, Vol. 356, P. 253–274.

19. Chebotarev, P., Deza, E. 2020, ”Hitting time quasi-metric and its forest representation“,

20. Optimization Letters, Vol. 14, P. 291-–307. https://doi.org/10.1007/s11590-018-1314-2

21. Chebotarev,P.Y., Shamis E.V. 1998, ”On proximity measures for graph vertices“, Automation

22. and Remote Control, Vol. 59, P. 1443—1459.

23. Deza, E., Deza, M., Dutour Sikiri´c, M. 2016, ”Generalizations of Finite Metrics and Cuts,“

24. World Scientific.

25. Deza, M., Deza, E. 2011, ”Cones of partial metrics“, Contributions to Discrete Mathematics,

26. Vol. 6, P. 26–47.

27. Deza, M. M., Deza, E. 2016, ”Encyclopedia of Distances,“ Springer, Berlin - Heidelberg.

28. Deza, M., Deza, E., Vidali, J. 2012, ”Cones of weighted and partial metrics“, in Proceedings of

29. the Internat. Conference on Algebra 2010: Advances in Algebraic Structures, P. 177–197.

30. Kirkland, S. J., Neumann, M. 2012, ”Group inverses of M-matrices and their applications,“

31. CRC Press.

32. Leighton, T., Rivest, R.L. 1983, ”The Markov chain tree theorem“, Computer Science Technical

33. Report MIT/LCS/TM-249, Laboratory of Computer Science, MIT, Cambridge, Mass.

34. Meyer, Jr., C. D. 1975, ”The role of the group generalized inverse in the theory of finite Markov

35. chains“, SIAM Review, Vol. 17, P. 443–464.