Kragujevac J. Math. 25 (2003) 55-63.

GRAPHS WITH EXTREMAL RANDIC INDEX
WHEN THE MINIMUM DEGREE OF VERTICES IS TWO

Ljiljana Pavlovic

Faculty of Science, Department of Mathematics, Radoja Domanovica 12,
P. O. Box 60, Kragujevac, Serbia and Montenegro

(Received March 10, 2003)

Abstract. Let G(2,n) be a connected graph without multiple edges which has n vertices and the minimum degree of vertices is 2. The Randic index is:

where du is the degree of vertex u and the summation goes over all edges (uv) of G. In this paper we offer another technique based on linear programming to find graphs on which the Randic index attains minimum value. The extremal graphs have n-2 vertices of degree 2 and 2 vertices of degree n-1.