Modelirovanie i Analiz Informatsionnykh Sistem
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Model. Anal. Inform. Sist.:
Year:
Volume:
Issue:
Page:
Find






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


Modelirovanie i Analiz Informatsionnykh Sistem, 2017, Volume 24, Number 4, Pages 410–414
DOI: https://doi.org/10.18255/1818-1015-2017-4-410-414
(Mi mais573)
 

Tree centroid properties clarification

Yu. A. Belov, S. I. Vovchok

P.G. Demidov Yaroslavl State University, 14 Sovetskaya str., Yaroslavl 150003, Russia
References:
Abstract: The paper is devoted to the tree centroid properties clarification. Attention of the authors was attracted by the popular problem of (binary) partition of a graph. The solution is known only by brute force algorithm. It was found that for a "economical" partition of a tree it makes sense to consider partitions in the neighborhood of centroid vertices, the definition of which is presented. In the paper, we proposed proofs connected with the limitation of their weight. It is also proved that if there are two centroid vertices in a tree, they are adjacent. In what follows, it is noted that three such vertices can not be in the tree. The corresponding statements are made. According to the first one, any vertex of a tree with a certain restriction on its weight is centroid. According to one of the points of the second statement, if there are two centroid vertices in the tree, the order of the tree is an even number. The third statement says that if a tree has a centroid vertex of limited weight, there is another centroid vertex of the same weight and adjacent to the first one. To prove the propositions, we consider the branch of greatest weight with a centroid vertex and take in this branch another vertex adjacent to the centroid. In this paper, Jordan's theorem is used, three images are used in the presentation of the material.
Keywords: centroid, tree centroid.
Received: 25.07.2017
Bibliographic databases:
Document Type: Article
UDC: 004.9
Language: Russian
Citation: Yu. A. Belov, S. I. Vovchok, “Tree centroid properties clarification”, Model. Anal. Inform. Sist., 24:4 (2017), 410–414
Citation in format AMSBIB
\Bibitem{BelVov17}
\by Yu.~A.~Belov, S.~I.~Vovchok
\paper Tree centroid properties clarification
\jour Model. Anal. Inform. Sist.
\yr 2017
\vol 24
\issue 4
\pages 410--414
\mathnet{http://mi.mathnet.ru/mais573}
\crossref{https://doi.org/10.18255/1818-1015-2017-4-410-414}
\elib{https://elibrary.ru/item.asp?id=29864494}
Linking options:
  • https://www.mathnet.ru/eng/mais573
  • https://www.mathnet.ru/eng/mais/v24/i4/p410
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Моделирование и анализ информационных систем
    Statistics & downloads:
    Abstract page:220
    Full-text PDF :235
    References:30
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024