Wiener index and saturated nodes of random exponential recursive ternary trees

Document Type : Original Article

Author

Mehri Javanian

Department of Statistics, Faculty of Sciences, University of Zanjan, Iran

10.22067/smps.2026.99021.1060

Abstract

‎‎An exponential recursive ternary tree (ERTT) is defined by the property that each node has three possible positions, referred to as external nodes, to which a child may be attached. At each growth step, every external node independently becomes a leaf with probability p, or remains external with probability 1-p. In this note, we study two quantities associated with ERTTs: the external Wiener index, defined as the sum of distances over all pairs of external nodes, and the number of saturated nodes, i.e., nodes that have three children. For these trees, we derive the expected value and the second moment of both the number of saturated nodes and the Wiener index. Subsequently, applying the martingale convergence theorem, we establish almost sure convergence and convergence in quadratic mean for a suitably scaled external Wiener index, which reflects the typical distance between two randomly chosen external nodes. Finally, using the contraction method, we prove convergence in distribution for a scaled version of the number of saturated nodes.

Keywords

C‎ontraction method

$L^2$-norm

Martingale convergence theorem

‎‎ ‎Wasserstein metric

Wiener index‎‎

---

References

1. Aguech, R., Bose, S., Mahmoud, H. and Zhang, Y. (2021). Some properties of exponential trees. International Journal of Computer Mathematics, 3, 16–32.
2. Ash, R. B. (1999). Probability and Measure Theory. Second Edition, Academic Press, New York.
   Chan, D. and Hughes, B., Leong, A. and Reed, W. (2003). Stochastically evolving networks. PhysicalReview E, 68, 066124.
3. Feng, Y., and Mahmoud, H. (2018). Profile of random exponential binary trees. Methodology and Computing in Applied Probability, 20, 575–587.
4. Grübel, R. and Michailow, I. (2015). Random recursive trees: a boundary theory approach. Electronic Journal of Probability, 20, 1–22.
5. Ghasemi, M., Javanian, M. and Imany Nabiyyi, R. (2023). Note on the exponential recursive k-ary trees. RAIRO-Theoretical Informatics and Applications, 57, 1–14.
6. Javanian, M. and Vahidi-Asl, M. Q. (2003). Note on the outdegree of a node in random recursive trees. Journal of Applied Mathematics and Computing, 13, 99–103.
7. Javanian, M. and Vahidi-Asl, M. Q. (2006). Depth of nodes in random recursive k-ary trees. Information Processing Letters, 98, 115–118.
8. Javanian, M. and Vahidi-Asl, M. Q. (2012). A strong law for the size of Yule m-oriented recursive trees. Journal of Applied Mathematics, Statistics and Informatics, 8, 67–72.
9. Javanian, M. (2013). Limit distribution of the degrees in scaled attachment random recursive trees. Bulletin of the Iranian Mathematical Society, 39, 1031–1036.
10. Javanian, M. (2014). On the external path length of random recursive k-ary trees. Italian Journal of Pure and Applied Mathematics, 31, 21–26.
11. Javanian, M. (2017). On the size of paged recursive trees. Discrete Mathematics, Algorithms and Applications, 9, 1–10.
12. Mahmoud, H. (2022). Profile of random exponential recursive trees. Methodology and Computing in Applied Probability, 24, 259–275.
13. Moon, J. W. (1974). The distance between nodes in recursive trees. London Mathematics Society Lectur Notes Series, 13, 125–132.
14. Najock, D. and Heyde, C. C. (1982). On the number of terminal vertices in certain random trees with an application to stemma construction in philology. Journal of Applied Probability, 19, 675–680.
15. Neininger, R. (2001). On a multivariate contraction method for random recursive structures with applications to quicksort. Random Structures and Algorithms, 19, 498–524.
16. Neininger, R. (2002). The Wiener index of random trees. Combinatorics, Probability and Computing, 11, 587–597.
17. Roesler, U. and Rueschendorf, L. (2001). The contraction method for recursive algorithms. Algorithmica, 29, 3–33.
18. Smythe, R. T. and Mahmoud, H. (1995). A survey of recursive trees. Theory of Probability and Mathematical Statistics, 51, 1–27.
19. Zhang, P. (2018). On several properties of plain-oriented recursive trees. arXiv:1706.02441v2.