Extremal graphs for the Randić index when minimum, maximum degrees and order of graphs are odd

Abstract

© 2014 Taylor & Francis. Let (Formula presented.) be the set of connected simple n-vertex graphs with minimum vertex degree (Formula presented.) and maximum vertex degree (Formula presented.). The Randić index (Formula presented.) of a graph G is defined by (Formula presented.) , where (Formula presented.) is the degree of vertex u and the summation extends over all edges uv of G. In this paper, we find for (Formula presented.) , and k, m, n are odd, extremal graphs in (Formula presented.) for which the Randić index attains its minimum value. We show that the extremal graphs have vertices of degree k, m and (Formula presented.) , the number of vertices of degree (Formula presented.) is one and the number of vertices of degree k is as close to (Formula presented.) as possible.