On the conjecture of Aouchiche and Hansen about the Randić index

Let G ( k , n ) be the set of connected simple n -vertex graphs with minimum vertex degree k . The Randić index R ( G ) of a graph G is defined by  R ( G ) = ∑ u v ∈ E ( G ) 1 d ( u ) d ( v ) , where d ( u ) is the degree of vertex u and the summation extends over all edges u v of G . In this paper we prove for k ≥ n 2 the conjecture of Aouchiche and Hansen about the graphs in G ( k , n ) for which the Randić index attains its minimum value. We show that the extremal graphs have only two degrees ( k and n − 1 ), and the number of vertices of degree k is as close to n 2 as possible. At the end we state the solutions of the more detailed optimization problems over graphs with arbitrary maximum vertex degree m , except in the case when k , m and n are odd numbers.