Variable neighborhood search for extremal graphs. 2. Finding graphs with extremal energy

The recently developed Variable Neighborhood Search (VNS) metaheuristic for combinatorial and global optimization is outlined together with its specia lization to the problem of finding extremal graphs with respect to one or m ore invariants and the corresponding program (AGX). We illustrate the poten tial of the VNS algorithm on the example of energy E, a graph invariant whi ch (in the case of molecular graphs of conjugated hydrocarbons) corresponds to the total pi-electron energy. Novel lower and upper bounds for E are su ggested by AGX and several conjectures concerning (molecular) graphs with e xtremal E values put forward. Moreover, most of the bounds are proved to ho ld.