The height of random k‐trees and related branching processes

DOI10.1002/RSA.20576MaRDI QIDQ5256388zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Colin Cooper, Ryuhei Uehara, Alan Frieze

Publication date 22 June 2015

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

random \(k\)-Apollonian networksrandom \(k\)-trees

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Abstract: We consider the height of random k-trees and k-Apollonian networks. These random graphs are not really trees, but instead have a tree-like structure. The height will be the maximum distance of a vertex from the root. We show that w.h.p. the height of random k-trees and k-Apollonian networks is asymptotic to clog t, where t is the number of vertices, and c=c(k) is given as the solution to a transcendental equation. The equations are slightly different for the two types of process. In the limit as k-->oo the height of both processes is asymptotic to log t/(k log 2).

Recommendations

• On the total heights of random rooted trees
• On the total heights of random rooted binary trees
• scientific article; zbMATH DE number 515653
• The height of random binary unlabelled trees
• Branching processes in the analysis of the heights of trees
• Asymptotics of heights in random trees constructed by aggregation
• The height of depth-weighted random recursive trees
• On the height of the primary path of random rooted trees

Cites work

• A note on the height of binary search trees
• A partial k-arboretum of graphs with bounded treewidth
• Ancestors and descendants in evolving k‐tree models
• Branching processes in the analysis of the heights of trees
• Degrees and distances in random and evolving Apollonian networks
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 3304503 (Why is no real title available?)
• scientific article; zbMATH DE number 3057307 (Why is no real title available?)
• scientific article; zbMATH DE number 3059214 (Why is no real title available?)
• Large deviations for the weighted height of an extended class of trees
• Note on the heights of random recursive trees and random m‐ary search trees
• On longest paths and diameter in random Apollonian networks
• Scale free properties of random \(k\)-trees
• The degree distribution of random \(k\)-trees
• The first birth problem for an age-dependent branching process

Cited in

(17)

• Heavy subtrees of Galton-Watson trees with an application to Apollonian networks
• The degree profile and weight in Apollonian networks and k-trees
• Randomized rumor spreading in poorly connected small-world networks
• Longest paths in random Apollonian networks and largest r-ary subtrees of random d-ary recursive trees
• The height of random binary unlabelled trees
• Justifying the small-world phenomenon via random recursive trees
• The distribution of height and diameter in random non-plane binary trees
• The Hitting Time for the Height of a Random Recursive Tree
• On the asymptotic joint distribution of height and width in random trees
• On the height of the primary path of random rooted trees
• scientific article; zbMATH DE number 515653 (Why is no real title available?)
• A note on the maximal degree in random k-trees
• Long Paths in Random Apollonian Networks
• Asymptotics of heights in random trees constructed by aggregation
• The connectivity-profile of random increasing \(k\)-trees
• Shape measures of random increasing k-trees
• scientific article; zbMATH DE number 2197876 (Why is no real title available?)

This page was built for publication: The height of random k‐trees and related branching processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5256388)