Let G(k, n) be the set of simple graphs (i.e. without multiple edges or loops) that have n vertices and the minimum degree of vertices is k. The Randić index of a graph G is: χ(G) = ∑(uv)(δuδv)−1/2, where δu is the degree of vertex u and the summation extends over all edges (uv) of G. Using linear programming, we find the extremal graphs or give good bounds for this index when the number nk of vertices of degree k is n−k+t, for 0≤t≤k and k≤n/2. We also prove that for nk⩾n−k, (k≤n/2) the minimum value of the Randić index is attained for the graph Kk,n−k*.
