The height of random k-trees and related branching processes

2013/09/16 by Cooper, Colin, Frieze, Alan, Uehara, Ryuhei
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1309.4342

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).

Related

• Random trees have height O(√(n))
• Universal height and width bounds for random trees
• Random Trees and General Branching Processes
• Scaling limit of trees with vertices of fixed degrees and heights
• A branching process approach to level-k phylogenetic networks