Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-16T06:13:35.126Z Has data issue: false hasContentIssue false

Longest paths in random Apollonian networks and largest r-ary subtrees of random d-ary recursive trees

Published online by Cambridge University Press:  24 October 2016

Andrea Collevecchio*
Affiliation:
Monash University
Abbas Mehrabian*
Affiliation:
University of Waterloo
Nick Wormald*
Affiliation:
Monash University
*
* Postal address: School of Mathematical Sciences, 9 Rainforest Walk, Clayton, VIC 3800, Australia.
*** Postal address: Department of Combinatorics and Optimization, University of Waterloo, 200 University Avenue West, Waterloo, ON N2L 3G1 Canada. Email address: amehrabi@uwaterloo.ca
* Postal address: School of Mathematical Sciences, 9 Rainforest Walk, Clayton, VIC 3800, Australia.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let r and d be positive integers with r<d. Consider a random d-ary tree constructed as follows. Start with a single vertex, and in each time-step choose a uniformly random leaf and give it d newly created offspring. Let 𝒯d,t be the tree produced after t steps. We show that there exists a fixed δ<1 depending on d and r such that almost surely for all large t, every r-ary subtree of 𝒯d,t has less than t δ vertices. The proof involves analysis that also yields a related result. Consider the following iterative construction of a random planar triangulation. Start with a triangle embedded in the plane. In each step, choose a bounded face uniformly at random, add a vertex inside that face and join it to the vertices of the face. In this way, one face is destroyed and three new faces are created. After t steps, we obtain a random triangulated plane graph with t+3 vertices, which is called a random Apollonian network. We prove that there exists a fixed δ<1, such that eventually every path in this graph has length less than t 𝛿, which verifies a conjecture of Cooper and Frieze (2015).

Information

Type
Research Papers
Copyright
Copyright © Applied Probability Trust 2016