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

Abstract

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)=∑ uv∈E(G)1d(u)d(v), where d(u) is the degree of vertex u and the summation extends over all edges uv of G. In this paper we prove for k<n2 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 n2 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. © 2012 Elsevier B.V. All rights reserved.