On 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 have only two degrees (kk and n−1n−1), and the number of vertices of degree kk is as close to n2 as possible. At the end we state the solutions of the more detailed optimization problems over graphs with arbitrary maximum vertex degree mm, except in the case when k,mk,m and nn are odd numbers.