Hostname: page-component-745bb68f8f-s22k5 Total loading time: 0 Render date: 2025-02-11T20:01:46.663Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Part of: Graph theory Combinatorial probability

Published online by Cambridge University Press:  24 October 2016

Andrea Collevecchio ,
Abbas Mehrabian  and
Nick Wormald
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).

Keywords

Random Apollonian networkrandom d-ary recursive treelongest pathEggenberger–Pólya urn

MSC classification

Primary: 05C80: Random graphs
Secondary: 60C05: Combinatorial probability 05C05: Trees
Type
Research Papers
Information
Journal of Applied Probability , Volume 53 , Issue 3 , September 2016 , pp. 846 - 856
Copyright
Copyright © Applied Probability Trust 2016 

References

[1] Albenque, M. and Marckert, J.-F. (2008).Some families of increasing planar maps.Electron. J. Prob. 13,1624–1671.Google Scholar
[2] Collevecchio, A.,Mehrabian, A. and Wormald, N. (2014).Longest paths in Apollonian networks and largest r-ary subtrees of random d-ary recursive trees. Available at http://arxiv.org/abs/1404.2425.Google Scholar
[3] Cooper, C. and Frieze, A. (2015).Long paths in random Apollonian networks.Internet Math. 11,308–318.CrossRefGoogle Scholar
[4] Cooper, C.,Frieze, A. and Uehara, R. (2014).The height of random $k$-trees and related branching processes.Random Structures Algorithms 45,675–702.Google Scholar
[5] Drmota, M. (2009).Random Trees: An Interplay Between Combinatorics and Probability.Springer,Vienna.CrossRefGoogle Scholar
[6] Ebrahimzadeh, E. et al. (2014).On longest paths and diameter in random Apollonian networks.Random Structures Algorithms 45,703–725.Google Scholar
[7] Frieze, A. and Tsourakakis, C. E. (2014).Some properties of random Apollonian networks.Internet Mathematics 10,162–187.Google Scholar
[8] Kolossváry, J. and Vág#x00F3;, L. (2013).Degrees and distances in random and evolving Apollonian networks.Preprint. Available at http://arxiv.org/abs/1310.3864v1.Google Scholar
[9] McDiarmid, C. (1998).Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics (Algorithms Combin. 16).Springer,Berlin,195–248.Google Scholar
[10] Mungan, M. (2011).Comment on ‘Apollonian networks: Simultaneously scale-free, small world, Euclidean, space filling, and with matching graphs’.Phys. Rev. Lett. 106,029802.Google Scholar
[11] Pemantle, R. (1988).Phase transition in reinforced random walk and RWRE on trees.Ann. Prob. 16,1229–1241.Google Scholar
[12] Zhang, Z.,Comellas, F.,Fertin, G. and Rong, L. (2006).High-dimensional Apollonian networks.J. Phys. A 39,1813–1818.Google Scholar
[13] Zhou, T.,Yan, G. and Wang, B.-H. (2005).Maximal planar networks with large clustering coefficient and power-law degree distribution.Phys. Rev. E 71,046141.Google Scholar