Chebyshevskii Sbornik
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Chebyshevskii Sb.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Chebyshevskii Sbornik, 2021, Volume 22, Issue 2, Pages 183–201
DOI: https://doi.org/10.22405/2226-8383-2018-22-2-183-201
(Mi cheb1029)
 

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

B. Mhanna

Moscow State Pedagogical University (Moscow)
References:
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.
Document Type: Article
UDC: 517
Language: Russian
Citation: B. Mhanna, “Matrix of relative forest accessibility of the oriented path and the oriented cycle”, Chebyshevskii Sb., 22:2 (2021), 183–201
Citation in format AMSBIB
\Bibitem{Mha21}
\by B.~Mhanna
\paper Matrix of relative forest accessibility of the oriented path and the oriented cycle
\jour Chebyshevskii Sb.
\yr 2021
\vol 22
\issue 2
\pages 183--201
\mathnet{http://mi.mathnet.ru/cheb1029}
\crossref{https://doi.org/10.22405/2226-8383-2018-22-2-183-201}
Linking options:
  • https://www.mathnet.ru/eng/cheb1029
  • https://www.mathnet.ru/eng/cheb/v22/i2/p183
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Statistics & downloads:
    Abstract page:87
    Full-text PDF :27
    References:23
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024