The Randić index and the diameter of graphs

AbstractThe Randić index R(G) of a graph G is defined as the sum of 1dudv over all edges uv of G, where du and dv 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 Pn 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)−12D(G)≥2−1, with equality if and only if G is a path with at least three vertices