Groupe d’études et de recherche en analyse des décisions


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

, et

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

Ce cahier a été révisé en avril 1999