![](https://d3ilqtpdwi981i.cloudfront.net/luXbrl5OUSy2W8h8LlT9qpuN-NA=/425x550/smart/https://bepress-attached-resources.s3.amazonaws.com/uploads/62/2b/3b/622b3b16-3dce-460b-b036-98a7826f0355/thumbnail_2d61fe81-941e-43b3-8a1a-58b32683c7c0.jpg)
Article
Randić index and the diameter of a graph
European Journal of Combinatorics
(2011)
Abstract
The Randić index R(G) of a nontrivial connected graph G is defined as the sum of the weights (d(u)d(v))−12 over all edges e=uv of G. We prove that R(G)≥d(G)/2, where d(G) is the diameter of G. This immediately implies that R(G)≥r(G)/2, which is the closest result to the well-known Graffiti conjecture R(G)≥r(G)−1 of Fajtlowicz (1988) [4], where r(G) is the radius of G. Asymptotically, our result approaches the bound R(G)d(G)≥n−3+222n−2 conjectured by Aouchiche, Hansen and Zheng (2007) [1].
Disciplines
Publication Date
April, 2011
DOI
10.1016/j.ejc.2010.12.002
Publisher Statement
This is a manuscript of an article published as Dvořák, Zdeněk, Bernard Lidický, and Riste Škrekovski. "Randić index and the diameter of a graph." European Journal of Combinatorics 32, no. 3 (2011): 434-442.. DOI: 10.1016/j.ejc.2010.12.002. Copyright 2010 Elsevier Ltd. Posted with permission.
Citation Information
Zdeněk Dvořák, Bernard Lidicky and Riste Škrekovski. "Randić index and the diameter of a graph" European Journal of Combinatorics Vol. 32 Iss. 3 (2011) p. 434 - 442 Available at: http://works.bepress.com/bernard-lidicky/23/