On the Randić index of graphs
MetadataShow full item record
For a given graph G = (V, E), the degree mean rate of an edge uv ∈ E is a half of the quotient between the geometric and arithmetic means of its end-vertex degrees d(u) and d(v). In this note, we derive tight bounds for the Randić index of G in terms of its maximum and minimum degree mean rates over
its edges. As a consequence, we prove the known conjecture that the average distance is bounded above by the Randić index for graphs with order n large enough, when the minimum degree δ is greater than (approximately) ∆1/3 , where ∆ is the maximum degree. As a by-product, this proves that almost all random (Erdös-Rényi) graphs satisfy the conjecture.
Is part ofDiscrete Mathematics, 2019, vol. 342, num. 10, p. 2792-2796
The following license files are associated with this item: