Notas:
|
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.
This research is partially supported by the project 017SGR1087 of the Agency for the Management of University and Research Grants (AGAUR) of the Government of Catalonia. This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie
Sk lodowska-Curie grant agreement No 734922. |