The Randic index and the diameter of graphs

Abstract

The {\it Randić index} $R(G)$ of a graph $G$ is defined as the sum of 1/\sqrt{d_ud_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-Hansen-Zheng 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)\ge \sqrt{2}-1$, with equality if and only if $G$ is a path with at least three vertices.

17 pages, accepted by Discrete Mathematics