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 \geq 3\) with Randić index \(R(G)\) and matching number \(\mu(G)\),
\[ R(G) – \mu(G) \leq \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) = \left\lfloor \frac{n+4}{2} \right\rfloor\), which was proposed by Aouchiche et al. In this paper, we confirm this conjecture for some classes of graphs.