Proof of the first part of 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 are complete split graphs Kk,n-k-, which have only two degrees, i.e. degree k and degree n-1, and the number of vertices of degree k is n-k, while the number of vertices of degree n-1 is k. At the end we generalize our results to graphs with prescribed maximum degree q.