Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4654017 | European Journal of Combinatorics | 2011 | 9 Pages |
Abstract
The Randić index R(G)R(G) of a nontrivial connected graph GG is defined as the sum of the weights (d(u)d(v))−12 over all edges e=uve=uv of GG. We prove that R(G)≥d(G)/2R(G)≥d(G)/2, where d(G)d(G) is the diameter of GG. This immediately implies that R(G)≥r(G)/2R(G)≥r(G)/2, which is the closest result to the well-known Graffiti conjecture R(G)≥r(G)−1R(G)≥r(G)−1 of Fajtlowicz (1988) [4], where r(G)r(G) is the radius of GG. Asymptotically, our result approaches the bound R(G)d(G)≥n−3+222n−2 conjectured by Aouchiche, Hansen and Zheng (2007) [1].
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Zdeněk Dvořák, Bernard Lidický, Riste Škrekovski,