On a Conjecture of Randić Index and Graph Radius


Hanyuan Deng, Zikai Tang, Jie Zhang




The \emph{Randić index} $R(G)$ of a graph $G$ is defined as the sum of $(d_id_j)^{-\frac12}$ over all edges $v_iv_j$ of $G$, where $d_i$ is the degree of the vertex $v_i$ in $G$. The \emph{radius} $r(G)$ of a graph $G$ is the minimum graph eccentricity of any graph vertex in $G$. Fajtlowicz in [S. Fajtlowicz, On conjectures of Graffiti, \emph{Discrete Math.} extbf{72} (1988) 113-118] conjectures $R(G)\geq r(G)-1$ for any connected graph $G$. A stronger version, $R(G)\geq r(G)$, is conjectured for all connected graphs except even paths by Caporossi and Hansen in [G. Caporossi, et al., Variable neighborhood search for extremal graphs 1: The Autographix system, \emph{Discrete Math.} extbf{212} (2000) 29-44]. In this paper, we make use of \emph{Harmonic index} $H(G)$, which is defined as the sum of $\frac2{d_i+d_j}$ over all edges $v_iv_j$ of $G$, to show that $R(G)\geq r(G)-\frac{31}{105}(k-1)$ for any graph with cyclomatic number $k\geq 1$, and $R(T)>r(T)+\frac1{15}$ for any tree except even paths. These results improve and strengthen the known results on these conjectures.