On the centroid of increasing trees

MaRDI QIDQ5207844zbMATH OpenFDO

Authors

Publication date 13 January 2020

Full work available at URL https://arxiv.org/abs/1802.09334, https://dmtcs.episciences.org/5691/pdf

zbMATH Keywords

limit distributioncentroidincreasing tree

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Distance in graphs (05C12)

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.

Recommendations

• scientific article; zbMATH DE number 1744100
• scientific article; zbMATH DE number 3952788
• On centroid branches of trees from certain families
• On the distribution of betweenness centrality in random trees
• On the distribution of distances between specified nodes in increasing trees

Cited in

(11)

• scientific article; zbMATH DE number 3952788 (Why is no real title available?)
• Contagion Source Detection in Epidemic and Infodemic Outbreaks: Mathematical Analysis and Network Algorithms
• Persistence of centrality in random growing trees
• scientific article; zbMATH DE number 1744100 (Why is no real title available?)
• Tree evolution processes for bucket increasing trees
• Centroids to centers in trees
• On centroid branches of trees from certain families
• Betweenness centrality in random trees
• Broadcasting on random recursive trees
• A new linear-time algorithm for centroid decomposition
• A minimax-condition for the characteristic center of a 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)