Neki rezultati o ekstremnim vrednostima Randićevog indeksa na grafovima

Abstract

This doctoral dissertation belongs to the Combinatorial Optimization applied to graphs, which includes elements of Linear and Quadratic Programming and Graph Theory. Combinatorial Optimization, as special mathematical discipline, is relatively young, although the first papers are more than two hundred years old. The fast development emerges after the second wold war, when grows need for optimization many tasks and processes. Since many objects could be represents as graph and combinatorial optimization solve extremal problems on discrete structures, there is narrow connection with Graph Theory. The subject of this dissertation is finding minimal value of the Randi´c index on n-vertex graphs G(k, n) with given minimum degree k of vertices and describing the structure of extremal graphs. This index was introduced 1975 by chemist Milan Randi´c in order to measure the branching of some molecules. There is a good correlations between this index and some physico-chemical properties of alcanes. There is, also, connection between Randi´c index and the eigenvalues of the Laplacian matrix of graph.