The Randic index and the diameter of graphs

The Randic index R(G) of a graph G is defined as the sum of 1/root d(u)d(v) over all edges uv 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/2D(G) >= root 2 - 1, with equality if and only if G is a path with at least three vertices. (C) 2011 Elsevier B.V. All rights reserved.