Matrix of relative forest accessibility of the oriented path and the oriented cycle
https://doi.org/10.22405/2226-8383-2021-22-2-183-201
Abstract
In this paper we consider the properties of the matrix of relative forest accessibility of the oriented cycle and the properties of the matrix of relative forest accessibility of the oriented path.
The introduction contains the history of the problem and provides an overview of the main ideas and results presented in the article.
The second section gives basic concepts of the graph theory and a ”graphical“ representation of the matrix of relative forest accessibility of the digraph Γ: F =(((𝑓𝑖𝑗))nxn)/𝑓 , 𝑖, 𝑗 = 1 . . . 𝑛, where 𝑓𝑖𝑗 is the number of spanning converging rooted forests of the digraph Γ, in which the vertices 𝑖 and 𝑗 belong to the same tree converging to 𝑗, and 𝑓 is the total number spanning converging rooted forests of the digraph Γ.
The third section deals with the construction and research of the matrix of relative forest accessibility of the oriented path 𝑃𝑛, 𝑛 ≥ 2. Examples of constructing the matrix of relative forest accessibility of oriented path for small values of 𝑛 are considered. Illustrations of the ”graphical“ procedure of building the matrix F are given. It is proved that the matrix of relative forest accessibility for the directed path 𝑃𝑛, 𝑛 ≥ 2, is related to the sequence 1, 2, 4, 8, 16, ..., 2𝑛, ... of powers of 2. In other words, the elements of 𝑓𝑖𝑗 that form the matrix are elements of the set
{1, 2, 22, ..., 2𝑛−1} filling the columns of the matrix: the first column consists of sequentially decreasing numbers 2𝑛−1, ..., 2, 1; the second column, starting at 0, contains in the second
place (the intersection with the main diagonal) the number 2𝑛−2, while the following elements are consecutively decreasing numbers 2𝑛−3, ..., 2, 1; the third column, containing zeros in two
positions above the main diagonal, contains in the third place (the intersection with the main diagonal) the number 2𝑛−2, while the following elements are sequentially decreasing numbers
2𝑛−3, ..., 2, etc. The value of 𝑓 is equal to 2𝑛−1.
In the fourth section, similar considerations for matrix of relative forest accessibility of the oriented cycle 𝐶𝑛, 𝑛 ≥ 3, are represented.
In the conclusion, the results of the work are summed up.
About the Author
Batool Mhanna
Moscow State Pedagogical University
Russian Federation
Russian Federation
graduate student
References
1. Deza, E., Mhanna, B. ”On special properties of some special quasi-metrics“, Chebyshevskii sbornik, Vol. 21 (1), P. 145 – 164.
2. Chebotarev, P., Agaev, R. 2011, ”Matrix forest theorem and Laplacian matrices of orgraphs“, М.: LAP LAMBERT Academic publishing.
3. Basin, S.L. 1963, ”The appearance of Fibonacci numbers and the Q matrix in electrical network theory“, Math. Magazine, vol. 36, P. 84 – 97.
4. Boesch, F. T., Prodinger, H. 1986, ”Spanning tree formulas and Chebyshev polynomials“, Graphs Combin, vol. 2, P. 191 – 200.
5. Chaiken, S. 1982, ”A combinatorial proof of the all minors matrix tree theorem“, SIAM J. Algebraic Discrete Methods, vol. 3, P. 319 – 329.
6. Chebotarev, P. Y., Shamis, E. V. 1997, ”The matrix-forest theorem and measuring relations in small social groups“, Automat. Remote Control, vol. 58, P. 1505 -– 1514.
7. Chebotarev, P. 2008, ”Spanning forests and the golden ratio“, Discrete Applied Mathematics, vol. 156, P. 813 – 821.
8. Chebotarev, P., Deza, E. 2020, ”Hitting time quasi-metric and its forest representation“, Optimization Letters, Vol. 14, P. 291 – 307.
9. Chebotarev, P., Agaev, R. 2002, ”Forest matrices around the Laplacian matrix“, Linear Algebra and its Applications, Vol. 356, P. 253 – 274.
10. Chebotarev, P. Y., Shamis E. V. 1998, ”On proximity measures for graph vertices“, Automation and Remote Control, Vol. 59, P. 1443 – 1459.
11. Hilton, A. J. W. 1974, ”Spanning trees and Fibonacci and Lucas numbers“, Fibonacci Quart, vol. 12, P. 259 -– 262.
12. Koshy, T. 2001, ”Fibonacci and Lucas Numbers“, Wiley-Interscience. New York.
13. Merris, R. 1997, ”Doubly stochastic graph matrices“, Publikacije Elektrotehnickog Fakulteta Univerzitet U Beogradu. Serija. Matematika, vol. 8, P. 64 – 71.
14. Merris, R. 1998, ”Doubly stochastic graph matrices II“, Linear and Multilinear Algebra, vol. 45, P. 275 -– 285.
15. Mowery, V. O. 1961, ”Fibonacci numbers and Tchebycheff polynomials in ladder networks“, IRE Trans. Circuit Theory, vol. 8, P. 167 – 168.
16. Myers, B. R. 1971, ”Number of spanning trees in a wheel“, IEEE Trans. Circuit Theory, vol. 18, P. 280 – 282.
17. Zhang, X. D. 2005, ”A note on doubly stochastic graph matrices“, Linear Algebra Appl, vol. 407, P. 196 – 200.
18. Zhang, X. D., Wu, J. X. 2005, ”Doubly stochastic matrices of trees“, Appl. Math. Lett, vol. 18, P. 339 – 343.
19. Zhang, Y., Yong, X. Golin, M. J. 2005, ”Chebyshev polynomials and spanning tree formulas for circulant and related graphs“, Discrete Math, vol. 298, P. 334 – 364.
Review
For citations:
Mhanna B. Matrix of relative forest accessibility of the oriented path and the oriented cycle. Chebyshevskii Sbornik. 2021;22(2):183-201. (In Russ.) https://doi.org/10.22405/2226-8383-2021-22-2-183-201
Views:
395
Email this article 