The height of random k‐trees and related branching processes1. Issue 4 (21st October 2014) - Cooper, Colin; Frieze, Alan; Uehara, Ryuhei
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 c log 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 →∞ the height of both processes is asymptotic to <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh21kb0xms" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />logt/(klog2)</alternatives>. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 675–702, 2014