Note on a relation between Randic index and algebraic connectivity

Abstract

A conjecture of AutoGraphiX on the relation between the Randić index $R$ and the algebraic connectivity $a$ of a connected graph $G$ is: $$\frac{R}{a}\le (\frac{n-3+2\sqrt{2}}{2})/(2(1-\cos \frac{\pi }{n}))$$ with equality if and only if $G$ is $P_n$, which was proposed by Aouchiche and Hansen [M. Aouchiche and P. Hansen, A survey of automated conjectures in spectral graph theory, {\it Linear Algebra Appl.} {\bf 432}(2010), 2293--2322]. We prove that the conjecture holds for all trees and all connected graphs with edge connectivity ${\kappa }^{\prime }(G)\ge 2$, and if ${\kappa }^{\prime }(G)=1$, the conjecture holds for sufficiently large $n$. The conjecture also holds for all connected graphs with diameter $D\le \frac{2(n-3+2\sqrt{2})}{{\pi }^2}$ or minimum degree $\delta \ge \frac{n}{2}$. We also prove $R\cdot a\ge \frac{8\sqrt{n-1}}{n{D}^2}$ and $R\cdot a\ge \frac{n\delta (2\delta -n+2)}{2(n-1)}$, and then $R\cdot a$ is minimum for the path if $D\le (n-1{)}^{1/4}$ or $\delta \ge \frac{n}{2}-1$.

6 pages