Article ID Journal Published Year Pages File Type
477803 European Journal of Operational Research 2007 9 Pages PDF
Abstract

Let G(k, n) be the set of connected graphs without multiple edges or loops which have n vertices and the minimum degree of vertices is k. The Randić index χ = χ(G) of a graph G   is defined by: χ=∑(uv)(δuδv)-1/2χ=∑(uv)(δuδv)-1/2, where δu is the degree of vertex u and the summation extends over all edges (uv) of G  . In this paper we prove the conjecture of Delorme, Favaron and Rautenbach about the graphs for which the Randić index attains its minimum value when k=n2. We show that the extremal graphs must have n − k vertices of degree k and k vertices of degree n − 1.

Related Topics
Physical Sciences and Engineering Computer Science Computer Science (General)
Authors
,