Longest paths in random Apollonian networks and largest \(r\)-ary subtrees of random \(d\)-ary recursive trees. (English) Zbl 1365.05072

Collevecchio, Andrea; Mehrabian, Abbas; Wormald, Nick

J. Appl. Probab. 53, No. 3, 846-856 (2016).

Consider the following iterative process for constructing a random planar triangulation: start with a single triangle; in each successive step, choose a bounded face uniformly at random, add a vertex inside that face and connect it to the vertices of that face to form three new faces. After \(t\) steps, this gives a random triangulated planar graph with \(t + 3\) vertices. Confirming a conjecture of C. Cooper and A. Frieze [“Long paths in random Apollonian networks”, Preprint, arXiv:1404.2425], the main result of this paper says that there exists \(\delta < 1\) such that eventually every path in this graph has length less than \(t^{\delta}\).
The paper also contains a similar result pertaining to the following model of a random \(d\)-ary tree: start with a single vertex; in each successive step, choose a leaf of the tree uniformly at random and give it \(d\) offspring. If \(r < d\), the authors show that there exists \(\delta < 1\) depending only on \(d\) and \(r\) such that almost surely, for all large \(t\), every \(r\)-ary subtree of the random tree produced after \(t\) steps has fewer than \(t^\delta\) vertices.

Reviewer: David Conlon (Oxford)

MSC:

05C12	Distance in graphs
05C38	Paths and cycles
05C80	Random graphs (graph-theoretic aspects)
05C82	Small world graphs, complex networks (graph-theoretic aspects)
05C10	Planar graphs; geometric and topological aspects of graph theory
05C05	Trees

Keywords:

random Apollonian networks; random \(d\)-ary recursive trees