Some properties of exponential trees

Abstract

Exponential recursive trees and exponential PORTs are introduced in H. Mahmoud (Profile of random exponential recursive trees. Methodology and Computing in Applied Probability (accepted) 2021). In that reference, the author investigates the order and node profile of these species. Several other equally important properties remain to be explored. The aim of the present manuscript is to establish fundamental properties concerning leaves (and their profile level by level) and distances in these trees. Some results fall back on the order of a tree. For the number of leaves in both flavours, we find (under appropriate scaling for each) a limit distribution uniquely characterized by inductively constructed moments. We find an $L^1$ limit for the scaled total (external) path length in an exponential recursive tree (PORT) in terms of the known distribution of the scaled order given in Mahmoud [11]. These total path lengths are indicative of the depth of a randomly chosen node (external node) in an exponential recursive tree (PORT).

Keywords:

• Network
• random graph
• degree profile
• limit law
• martingale

AMS subject classifications:

• Primary: 05082
• 90B15
• Secondary: 60C05
• 60F05
• 60G42

Acknowledgments

The authors are indebted to anonymous referees, whose constructive critique sharpened the arguments and led to a better overall exposition.

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1 Note the double randomness, a random node is chosen in a random tree.