Hostname: page-component-745bb68f8f-d8cs5 Total loading time: 0 Render date: 2025-02-06T19:43:37.838Z Has data issue: false hasContentIssue false
  • English
  • Français

The Gini index of random trees with an application to caterpillars

Part of: Chemistry Combinatorial probability Graph theory

Published online by Cambridge University Press:  15 September 2017

Hrishikesh Balaji  and
Hosam Mahmoud
Hrishikesh Balaji*
Affiliation:
Winston Churchill High School
Hosam Mahmoud*
Affiliation:
The George Washington University
*
* Postal address: Winston Churchill High School, Potomac, MD 20854, USA. Email address: hrishikeshbalaji@gmail.com
** Postal address: Department of Statistics, The George Washington University, Washington, D.C. 20052, USA. Email address: hosam@gwu.edu
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.

We propose two distance-based topological indices (level index and Gini index) as measures of disparity within a single tree and within tree classes. The level index and the Gini index of a single tree are measures of balance within the tree. On the other hand, the Gini index for a class of random trees can be used as a comparative measure of balance between tree classes. We establish a general expression for the level index of a tree. We compute the Gini index for two random classes of caterpillar trees and see that a random multinomial model of trees with finite height has a countable number of limits in [0, ⅓], whereas a model with independent level numbers fills the spectrum (0, ⅓].

Keywords

Random treechemical treecombinatorial probabilityGini indexWiener indextopological index

MSC classification

Primary: 05C05: Trees 05C12: Distance in graphs 92E10: Molecular structure (graph-theoretic methods, methods of differential topology, etc.)
Secondary: 60C05: Combinatorial probability
Type
Research Papers
Information
Journal of Applied Probability , Volume 54 , Issue 3 , September 2017 , pp. 701 - 709
Copyright
Copyright © Applied Probability Trust 2017 

References

[1] Ceriani, L. and Verme, P. (2012). The origins of the Gini index: extracts from Variabilità e Mutabilità (1912) by Corrado Gini. J. Econom. Inequality 10, 421–443. CrossRefGoogle Scholar
[2] El-Basil, S. (1990). Caterpillar (Gutman) trees in chemical graph theory. In Advances in the Theory of Benzenoid Hydrocarbons (Topics Current Chem. 153), Springer, Berlin, pp. 273–289. Google Scholar
[3] Feng, Q. and Hu, Z. (2011). On the Zagreb index of random recursive trees. J. Appl. Prob. 48, 1189–1196. CrossRefGoogle Scholar
[4] Feng, Q., Mahmoud, H. M. and Panholzer, A. (2008). Limit laws for the Randić index of random binary tree models. Ann. Inst. Statist. Math. 60, 319–343. CrossRefGoogle Scholar
[5] Flajolet, P. and Prodinger, H. (1987). Level number sequences for trees. Discrete Math. 65, 149–156. CrossRefGoogle Scholar
[6] Gastwirth, J. L. (1972). The estimation of the Lorenz curve and Gini index. Rev. Econom. Statist. 54, 306–316. CrossRefGoogle Scholar
[7] Gini, C. (1912). Veriabilità e Mutabilità. Cuppini, Bologna. Google Scholar
[8] Gutman, I. (1977). Topological properties of benzenoid systems. Theoretica Chimica Acta 45, 309–315. CrossRefGoogle Scholar
[9] Harary, F. and Schwenk, A. J. (1973). The number of caterpillars. Discrete Math. 6, 359–365. CrossRefGoogle Scholar
[10] Neininger, R. (2002). The Wiener index of random trees. Combinatorics Prob. Comput. 11, 587–597. CrossRefGoogle Scholar
[11] Schmuck, N. S., Wagner, S. G. and Wang, H. (2012). Greedy trees, caterpillars, and Wiener-type graph invariants. MATCH Commun. Math. Comput. Chem. 68, 273–292. Google Scholar
[12] Tangora, M. C. (1991). Level number sequences of trees and the lambda algebra. Europ. J. Combinatorics 12, 433–443. CrossRefGoogle Scholar