On Randic Index and the Matching Number

Abstract

The Randić index of a graph $G$, denoted by $R(G)$, is defined as the sum of $\frac{1}{d(u)d(v)}$ over all edges $uv$ of $G$, where $d(u)$ denotes the degree of a vertex $u$ in $G$. Denote by $\nu (G)$ the matching number, i.e., the number of edges in a maximum matching of $G$. A conjecture of AutoGraphiX on the relation between the Randić index and the matching number of a connected graph $G$ states: for any connected graph of order $n\ge 3$ with Randić index $R(G)$ and matching number $\mu (G)$,
$$R(G)–\mu (G)\le \sqrt{\lfloor \frac{n+4}{7}\rfloor \lfloor \frac{6n+2}{7}\rfloor }-\lfloor \frac{n+4}{7}\rfloor$$
with equality if and only if $G$ is a complete bipartite graph $K_{p,q}$ with $p=\mu (G)=\lfloor \frac{n+4}{2}\rfloor$, which was proposed by Aouchiche et al. In this paper, we confirm this conjecture for some classes of graphs.