The Randić index and the diameter of graphs

The Randić index R ( G ) of a graph G is defined as the sum of 1 d u d v over all edges u v of G , where d u and d v are the degrees of vertices u and v , respectively. Let D ( G ) be the diameter of G when G is connected. Aouchiche et al. (2007) [1] conjectured that among all connected graphs G on n vertices the path P n achieves the minimum values for both R ( G ) / D ( G ) and R ( G ) − D ( G ) . We prove this conjecture completely. In fact, we prove a stronger theorem: If G is a connected graph, then R ( G ) − 1 2 D ( G ) ≥ 2 − 1 , with equality if and only if G is a path with at least three vertices.