Group for Research in Decision Analysis

G-98-67

Variable Neighborhood Search for Extremal Graphs. 4. Chemical Trees with Extremal Connectivity Index

, , and

By means of the variable neighborhood search algorithm, a newly designed heuristic approach to combinatorial optimization, we established the structure of the chemical trees possessing extremal (maximal and minimal) values for the Randic connectivity index (). These findings were eventually corroborated by rigorous mathematical proofs. As could have been anticipated, the n vertex tree with maximum is the path. The n-vertex chemical tree with minimum -value is not unique. The structures of such chemical trees (which should be considered as the graph representations of the most branched alkanes) are fully characterized.

, 18 pages

This cahier was revised in April 1999