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.
Published December 1998 , 18 pages
This cahier was revised in April 1999