On the Randić index

Delorme, Charles
Favaron, Odile
Rautenbach, Dieter

Open link

Publication date

November 2002

DOI

10.1016/S0012-365X(02)00256-X

Publisher

Elsevier Science B.V.

Abstract

AbstractThe Randić index R(G) of a graph G=(V,E) is the sum of (d(u)d(v))−1/2 over all edges uv∈E of G. Bollobás and Erdős (Ars Combin. 50 (1998) 225) proved that the Randić index of a graph of order n without isolated vertices is at least n−1. They asked for the minimum value of R(G) for graphs G with given minimum degree δ(G). We answer their question for δ(G)=2 and propose a related conjecture. Furthermore, we prove a best-possible lower bound on the Randić index of a triangle-free graph G with given minimum degree δ(G)