On the Randić index of graphs

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 Randic index of G in terms of its maximum and minimum degree mean rates over...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2019-10, Vol.342 (10), p.2792-2796
Main Author: Dalfó, C.
Format: Article
Language:English
Subjects:
Connectivity index
Edge degree rate
Grafs, Teoria de
Graph theory
Matemàtica discreta
Matemàtiques i estadística
Mean distance
Randic index
Teoria de grafs
Àrees temàtiques de la UPC
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 Randic 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 Randic index for graphs with order n large enough, when the minimum degree d is greater than (approximately) ¿1/3 , where ¿ is the maximum degree. As a by-product, this proves that almost all random (Erdos–Rényi) graphs satisfy the conjecture Peer Reviewed
ISSN:0012-365X
DOI:10.1016/j.disc.2018.08.020