The height of random k‐trees and related branching processes1. Issue 4 (6th February 2015)

• Record Type: Journal Article
• Authors: Cooper, Colin; Frieze, Alan; Uehara, Ryuhei
• Is Part Of: Random structures & algorithms. Volume 45:Issue 4(2014)
• Page Start: 675
• Page End: 702
• Publication Date: 2015-02-06
• Subjects: Random k‐trees -- Random k‐Apollonian networks; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20576
• Languages: English
• ISSNs: 1042-9832

Abstract

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 log t / ( k log 2 ) . © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 675–702, 2014