Randić index, diameter and the average distance

Abstract

The Randić index of a graph $G$, denoted by $R(G)$, is defined as the sum of $1/\sqrt{d(u)d(v)}$ over all edges $uv$ of $G$, where $d(u)$ denotes the degree of a vertex $u$ in $G$. In this paper, we partially solve two conjectures on the Randić index $R(G)$ with relations to the diameter $D(G)$ and the average distance $\mu (G)$ of a graph $G$. We prove that for any connected graph $G$ of order $n$ with minimum degree $\delta (G)$, if $\delta (G)\ge 5$, then $R(G)-D(G)\ge \sqrt{2}-\frac{n+1}{2}$; if $\delta (G)\ge n/5$ and $n\ge 15$, $\frac{R(G)}{D(G)}\ge \frac{n-3+2\sqrt{2}}{2n-2}$ and $R(G)\ge \mu (G)$. Furthermore, for any arbitrary real number $\epsilon (0<\epsilon <1)$, if $\delta (G)\ge \epsilon n$, then $\frac{R(G)}{D(G)}\ge \frac{n-3+2\sqrt{2}}{2n-2}$ and $R(G)\ge \mu (G)$ hold for sufficiently large $n$.

7 pages