Skip to main content
Article
Randić index and the diameter of a graph
European Journal of Combinatorics (2011)
  • Zdeněk Dvořák, Charles University
  • Bernard Lidicky, Charles University
  • Riste Škrekovski, University of Ljubljana
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].
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/