Back to Search
Start Over
DEGREE-BASED GINI INDEX FOR GRAPHS
- Source :
- Probability in the Engineering and Informational Sciences. 34:157-171
- Publication Year :
- 2019
- Publisher :
- Cambridge University Press (CUP), 2019.
-
Abstract
- In Balaji and Mahmoud [1], the authors introduced a distance-based Gini index for rooted trees. In this paper, we introduce a degree-based Gini index (or just simply degree Gini index) for graphs. The latter index is a topological measure on a graph capturing the proximity to regular graphs. When applied across the random members of a class of graphs, we can identify an average measure of regularity for the class. Whence, we can compare the classes of graphs from the vantage point of closeness to regularity.We develop a simplified computational formula for the degree Gini index and study its extreme values. We show that the degree Gini index falls in the interval [0, 1). The main focus in our study is the degree Gini index for the class of binary trees. Via a left-packing transformation, we show that, for an arbitrary sequence of binary trees, the Gini index has inferior and superior limits in the interval [0, 1/4]. We also show, via the degree Gini index, that uniform rooted binary trees are more regular than binary search trees grown from random permutations.
- Subjects :
- Statistics and Probability
Binary tree
Index (economics)
Degree (graph theory)
05 social sciences
Wiener index
Management Science and Operations Research
01 natural sciences
Industrial and Manufacturing Engineering
Combinatorics
010104 statistics & probability
Binary search tree
Topological index
0502 economics and business
Random tree
Interval (graph theory)
050207 economics
0101 mathematics
Statistics, Probability and Uncertainty
Mathematics
Subjects
Details
- ISSN :
- 14698951 and 02699648
- Volume :
- 34
- Database :
- OpenAIRE
- Journal :
- Probability in the Engineering and Informational Sciences
- Accession number :
- edsair.doi...........a8f406c0c2c04a2ada6c4a4ad322a927