Kevin Durant ; Stephan Wagner - On the centroid of increasing trees

dmtcs:4325 - Discrete Mathematics & Theoretical Computer Science, August 27, 2019, vol. 21 no. 4 - https://doi.org/10.23638/DMTCS-21-4-8
On the centroid of increasing treesArticle

Authors: Kevin Durant ; Stephan Wagner

    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.


    Volume: vol. 21 no. 4
    Section: Combinatorics
    Published on: August 27, 2019
    Accepted on: August 3, 2019
    Submitted on: February 27, 2018
    Keywords: Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 1487 times.
    This article's PDF has been downloaded 347 times.