Please use this identifier to cite or link to this item: https://scidar.kg.ac.rs/handle/123456789/10364
Title: On the conjecture of Aouchiche and Hansen about the Randić index
Authors: Liu B.
Pavlović, Ljiljana
Divnić T.
Liu J.
Stojanovic, Mirjana
Issue Date: 2013
Abstract: Let G(k,n) be the set of connected simple n-vertex graphs with minimum vertex degree k. The Randić index R(G) of a graph G is defined by R(G)=∑ uv∈E(G)1d(u)d(v), where d(u) is the degree of vertex u and the summation extends over all edges uv of G. In this paper we prove for k<n2 the conjecture of Aouchiche and Hansen about the graphs in G(k,n) for which the Randić index attains its minimum value. We show that the extremal graphs have only two degrees (k and n-1), and the number of vertices of degree k is as close to n2 as possible. At the end we state the solutions of the more detailed optimization problems over graphs with arbitrary maximum vertex degree m, except in the case when k,m and n are odd numbers. © 2012 Elsevier B.V. All rights reserved.
URI: https://scidar.kg.ac.rs/handle/123456789/10364
Type: article
DOI: 10.1016/j.disc.2012.10.012
ISSN: 0012-365X
SCOPUS: 2-s2.0-84868474487
Appears in Collections:Faculty of Science, Kragujevac

Page views(s)

510

Downloads(s)

9

Files in This Item:
File Description SizeFormat 
PaperMissing.pdf
  Restricted Access
29.86 kBAdobe PDFThumbnail
View/Open


Items in SCIDAR are protected by copyright, with all rights reserved, unless otherwise indicated.