Premium
The linear programming approach to the Randić index
Author(s) -
Pavlović Ljiljana
Publication year - 2007
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2007.00612.x
Subject(s) - combinatorics , mathematics , graph , vertex (graph theory) , simple graph , degree (music) , discrete mathematics , physics , acoustics
Let G ( k , n ) be the set of simple graphs (i.e. without multiple edges or loops) that have n vertices and the minimum degree of vertices is k . The Randić index of a graph G is: , where δ u is the degree of vertex u and the summation extends over all edges ( uv ) of G . Using linear programming, we find the extremal graphs or give good bounds for this index when the number n k of vertices of degree k is n − k + t , for 0 t k and k n /2. We also prove that for n k n − k , ( k n /2) the minimum value of the Randić index is attained for the graph .