Matrix of relative forest accessibility of the oriented path and the oriented cycle

B. Mhanna

Čebyševskij sbornik, Tome 22 (2021) no. 2, pp. 183-201.

Résumé

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 $ \Gamma $: $ \mathbb {F} = \dfrac {((f_ {ij}))} {f}, i, j= 1\dots n$, where $ f_{ij} $ is the number of spanning converging rooted forests of the digraph $ \Gamma $, in which the vertices $ i $ and $ j $ belong to the same tree converging to $ j $, and $ f $ is the total number spanning converging rooted forests of the digraph $ \Gamma $. The third section deals with the construction and research of the matrix of relative forest accessibility of the oriented path $ \overrightarrow {P_ {n}} $, $ n \geq 2 $. Examples of constructing the matrix of relative forest accessibility of oriented path for small values of $ n $ are considered. Illustrations of the "graphical" procedure of building the matrix $ \mathbb{F} $ are given. It is proved that the matrix of relative forest accessibility for the directed path $ \overrightarrow {P_ {n}}, n \geq 2 $, is related to the sequence $ 1, 2, 4, 8, 16, \dots, 2^{n},\dots $ of powers of $2$. In other words, the elements of $ f_ {ij} $ that form the matrix are elements of the set $ \{1, 2, 2 ^ 2, \dots, 2^{n-1} \} $ filling the columns of the matrix: the first column consists of sequentially decreasing numbers $ 2^{n-1}, \dots, 2, 1 $; the second column, starting at $0$, contains in the second place (the intersection with the main diagonal) the number $ 2 ^ {n-2} $, while the following elements are consecutively decreasing numbers $ 2^{n-3}, \dots, 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^{n-2} $, while the following elements are sequentially decreasing numbers $ 2 ^ {n- 3}, \dots, 2 $, etc. The value of $ f $ is equal to $ 2^{n-1} $. In the fourth section, similar considerations for matrix of relative forest accessibility of the oriented cycle $\overrightarrow{C_n}$, $n\geq 3$, are represented. In the conclusion, the results of the work are summed up.

Détail

Keywords: the matrix of relative forest accessibility, oriented path, oriented cycle, graph, digraph, spanning converging forests, Mersenne number.

Bibliographie

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

[2] Chebotarev P.Yu., Agaev R.P., Matrichnaya teorema o lesakh i laplasovskie matritsy orgrafov, LAP LAMBERT Academic publishing, M., 2011

[3] Basin S.L., “The appearance of Fibonacci numbers and the Q matrix in electrical network theory”, Math. Magazine, 36 (1963), 84–97 | DOI | MR | Zbl

[4] Boesch F. T., Prodinger H., “Spanning tree formulas and Chebyshev polynomials”, Graphs Combin., 2 (1986), 191–200 | DOI | MR | Zbl

[5] Chaiken S., “A combinatorial proof of the all minors matrix tree theorem”, SIAM J. Algebraic Discrete Methods, 3 (1982), 319–329 | DOI | MR | Zbl

[6] Chebotarev P. Y., Shamis E. V., “The matrix-forest theorem and measuring relations in small social groups”, Automat. Remote Control, 58 (1997), 1505–1514 | MR | Zbl

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

[8] Chebotarev P., Deza E., “Hitting time quasi-metric and its forest representation”, Optimization Letters, 14 (2020), 291–307 | 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.Y., Shamis E.V., “On proximity measures for graph vertices”, Automation and Remote Control, 59 (1998), 1443–1459 | MR | Zbl

[11] Hilton A. J. W., “Spanning trees and Fibonacci and Lucas numbers”, Fibonacci Quart, 12 (1974), 259–262 | MR | Zbl

[12] Koshy T., Fibonacci and Lucas Numbers, Wiley-Interscience, New York, 2001 | Zbl

[13] Merris R., “Doubly stochastic graph matrices”, Publikacije Elektrotehnickog Fakulteta Univerzitet U Beogradu. Serija. Matematika, 8 (1997), 64–71 | MR | Zbl

[14] Merris R., “Doubly stochastic graph matrices II”, Linear and Multilinear Algebra, 45 (1998), 275–285 | DOI | MR | Zbl

[15] Mowery V. O., “Fibonacci numbers and Tchebycheff polynomials in ladder networks”, IRE Trans. Circuit Theory, 8 (1961), 167–168 | DOI

[16] Myers B. R., “Number of spanning trees in a wheel”, IEEE Trans. Circuit Theory, 18 (1971), 280–282 | DOI

[17] Zhang X. D., “A note on doubly stochastic graph matrices”, Linear Algebra Appl, 407 (2005), 196–200 | DOI | MR | Zbl

[18] Zhang X. D., Wu J. X., “Doubly stochastic matrices of trees”, Appl. Math. Lett., 18 (2005), 339–343 | DOI | MR | Zbl

[19] Zhang Y., Yong X., Golin M.J., “Chebyshev polynomials and spanning tree formulas for circulant and related graphs”, Discrete Math., 298 (2005), 334–364 | DOI | MR | Zbl