On a Conjecture of Randic Index and Graph Radius

Hanyuan Deng, Zikai Tang, Jie Zhang


The {\em Randi\'{c} index} $R(G)$ of a graph $G$ is defined
as the sum of $(d_i d_j)^{-\frac{1}{2}}$ over all edges $v_i v_j$ of $G$, where $d_i$ is the degree of the vertex $v_i$ in $G$. The {\em radius} $r(G)$ of a graph $G$ is the minimum graph eccentricity of any graph vertex in $G$. Fajtlowicz~\cite{fa} conjectures $R(G) \ge r(G)-1$ for all connected graph $G$. A stronger version, $R(G) \ge r(G)$, is conjectured by Caporossi and Hansen~\cite{ch} for all connected graphs except even paths.
In this paper, we make use of {\em Harmonic index} $H(G)$, which is defined as the sum of $\frac{2}{d_i+d_j}$ over all edges $v_i v_j$ of $G$, to show that $R(G) \ge r(G)-\frac{31}{105}(k-1)$ for any graph with cyclomatic number $k\ge 1$, and $R(T)> r(T)+\frac{1}{15}$ for any tree except even paths. These results improve and strengthen the known results on these conjectures.

Full Text:



  • There are currently no refbacks.