RUS  ENG
Full version
JOURNALS // Chebyshevskii Sbornik // Archive

Chebyshevskii Sb., 2021 Volume 22, Issue 2, Pages 183–201 (Mi cheb1029)

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

B. Mhanna

Moscow State Pedagogical University (Moscow)

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 $ \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.

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

UDC: 517

DOI: 10.22405/2226-8383-2018-22-2-183-201



© Steklov Math. Inst. of RAS, 2024