Carnegie Mellon University
Browse
file.pdf (368.04 kB)

The height of random k-trees and related branching processes

Download (368.04 kB)
journal contribution
posted on 2014-05-16, 00:00 authored by Colin Cooper, Alan FriezeAlan Frieze, Ryuhei Uehara

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

History

Publisher Statement

This is the accepted version of the article which has been published in final form at http://dx.doi.org/10.1002/rsa.20576

Date

2014-05-16

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC