Abstract: A centroid node in a tree is a node for which the sum of the distances to all other nodes attains its minimum, or equivalently a node with the property that none of its branches contains more than half of the other nodes. We generalise some known results regarding the behaviour of centroid nodes in random recursive trees (due to Moon) to the class of very simple increasing trees, which also includes the families of plane-oriented and -ary increasing trees. In particular, we derive limits of distributions and moments for the depth and label of the centroid node nearest to the root, as well as for the size of the subtree rooted at this node.
Recommendations
Cited in
(12)- On centroid branches of trees from certain families
- Broadcasting on random recursive trees
- scientific article; zbMATH DE number 3952788 (Why is no real title available?)
- Centroids to centers in trees
- scientific article; zbMATH DE number 1744100 (Why is no real title available?)
- Persistence of centrality in random growing trees
- A minimax-condition for the characteristic center of a tree
- Betweenness centrality in random trees
- Tree evolution processes for bucket increasing trees
- Contagion Source Detection in Epidemic and Infodemic Outbreaks: Mathematical Analysis and Network Algorithms
- A new linear-time algorithm for centroid decomposition
- Estimating the history of a random recursive tree
This page was built for publication: On the centroid of increasing trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207844)
