On the centroid of increasing trees

zbMATH Open1430.05014arXiv1802.09334MaRDI QIDQ5207844FDOQ5207844

Authors:

Publication date: 13 January 2020

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.

Full work available at URL: https://arxiv.org/abs/1802.09334

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

zbMATH Keywords

limit distributioncentroidincreasing tree

Mathematics Subject Classification ID

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

Cited In (10)

• Title not available (Why is that?)
• Contagion Source Detection in Epidemic and Infodemic Outbreaks: Mathematical Analysis and Network Algorithms
• Persistence of centrality in random growing trees
• Title not available (Why is that?)
• 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 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)