Proof of the first part of the conjecture of Aouchiche and Hansen about the Randić index

Let G(k,n)G(k,n) be the set of connected simple nn-vertex graphs with minimum vertex degree kk. The Randić index R(G)R(G) of a graph GG is defined by: R(G)=∑uv∈E(G)1d(u)d(v), where d(u)d(u) is the degree of vertex uu and the summation extends over all edges uvuv of GG. In this paper we prove for k≤n2 the conjecture of Aouchiche and Hansen about the graphs in G(k,n)G(k,n) for which the Randić index attains its minimum value. We show that the extremal graphs are complete split graphs Kk,n−k∗, which have only two degrees, i.e. degree kk and degree n−1n−1, and the number of vertices of degree kk is n−kn−k, while the number of vertices of degree n−1n−1 is kk. At the end we generalize our results to graphs with prescribed maximum degree qq.