On the centroid of increasing trees
Date
2019
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Episciences.org
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 d-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.
Description
CITATION: Durant, K. & Wagner, S. 2019. On the centroid of increasing trees. Discrete Mathematics & Theoretical Computer Science, 21(4). doi:10.23638/DMTCS-21-4-8
The original publication is available at https://dmtcs.episciences.org/
The original publication is available at https://dmtcs.episciences.org/
Keywords
Centroid, Center of mass, Increasing trees (Mathematics), Nodes (Vertices), Limit theorems (Probability theory)
Citation
Durant, K. & Wagner, S. 2019. On the centroid of increasing trees. Discrete Mathematics & Theoretical Computer Science, 21(4). doi:10.23638/DMTCS-21-4-8