Clarification of the Properties of a Tree Centroid

Аннотация

This paper is devoted to clarification of tree centroid properties. The authors attention was drawn to the popular problem of a (binary) partition of a graph, whose solution is known only by a brute force algorithm. It was found that for an “efficient” partition of the 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 proven that if there are two centroid vertices in a tree, they are adjacent. In what follows, it is noted that three such vertices cannot be in a tree. The corresponding statements are made. According to the first one, any vertex of a tree with a certain restriction on its weight is a centroid. According to one of the points of the second statement, if there are two centroid vertices in a 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, adjacent to the first one. To prove these statements, we consider a branch of the greatest weight with a centroid vertex and take another vertex adjacent to the centroid in this branch. In this paper, Jordan’s theorem is used; three images are used to illustrate the material.