Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
477803 | European Journal of Operational Research | 2007 | 9 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Ljiljana Pavlović,